可以套模板的多重背包问题
因为背包容量和物品种类数都最大10000，暴力dp 需要一亿次，本来以为可能超一秒了。结果...可能是每次做的事情都太傻瓜了吧。
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 4176 KB]
Test 2: TEST OK [0.000 secs, 4176 KB]
Test 3: TEST OK [0.000 secs, 4176 KB]
Test 4: TEST OK [0.000 secs, 4176 KB]
Test 5: TEST OK [0.000 secs, 4176 KB]
Test 6: TEST OK [0.000 secs, 4176 KB]
Test 7: TEST OK [0.014 secs, 4176 KB]
Test 8: TEST OK [0.056 secs, 4176 KB]
Test 9: TEST OK [0.084 secs, 4176 KB]
Test 10: TEST OK [0.098 secs, 4176 KB]
Test 11: TEST OK [0.000 secs, 4176 KB]
Test 12: TEST OK [0.000 secs, 4176 KB]
All tests OK.
/*
ID: ufoshen1
LANG: C++
TASK: inflate
*/
#include <cstdio>
#include <cstdlib>
#define max(a,b) ((a) > (b)? (a): (b))
int main(){
FILE *fin = fopen("inflate.in", "r");
FILE *fout = fopen("inflate.out", "w");
const int maxM = 10000, maxN = 10000; //最大时间 最大种类数
int dp[maxM + 1], M, N;
int score[maxN], time[maxN];
// 读入
fscanf(fin, "%d %d", &M, &N);
for(int i = 0; i < N; i ++){
fscanf(fin, "%d %d", score + i, time + i);
}
// 初始化
for(int i = 0; i <= M; i ++){
dp[i] = 0;
}
// 多重背包问题的 dp
for(int i = 0; i < N; i ++){
for(int j = time[i]; j <= M; j ++){
dp[j] = max(dp[j], dp[j - time[i]] + score[i]);
}
}
fprintf(fout, "%d\n", dp[M]);
return 0;
}
代码我都不好意思放了……回去看了下之前写的背包问题，就直接过了……
