1 条题解
-
0
仅仅多了一维而已(+一个小优化) 好好看看01背包一级一维背包就行了
#include<bits/stdc++.h> using namespace std; int n,O,N; int dp[101][101]; int o2[1010],n2[1010],w[1001]; int main() { scanf("%d%d%d",&O,&N,&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&o2[i],&n2[i],&w[i]); } memset(dp,127,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=O;j>=0;j--) { for(int k=N;k>=0;k--) { int t1=j+o2[i],t2=k+n2[i]; if(t1>O) t1=O; if(t2>N) t2=N; dp[t1][t2]=min(dp[t1][t2],dp[j][k]+w[i]);//优化 } } } printf("%d",dp[O][N]); return 0; }
- 1
信息
- ID
- 467
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 19
- 已通过
- 7
- 上传者