/gotoproblem?pid=2063
（1）上限 m 一直上升的 n 次01背包问题，比一般的01背包多了一重循环；
（2）本题出现了各种错误：1）刚开始，没注意 m 变大会影响 dp 的上限，开了个dp[1100000]， RE；
2）由于 m 的只比较大， 开了个dp[8000000]，MLE（内存不够）；
3）改小为dp[5000000], TLE（超时）；
4）为什么要开这么大数组，好像是因为 m 太大了。。
重新读题，
The value of a bond is always a multiple of $1 000.
终于降下了内存，少了1000倍的无用功。
具体代码：
View Code
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int N=50000;const int Inf=1<<29;int n, m, d;int dp[N];int v[15], in[15];int main(){int i, j, k, t;while(scanf("%d", &t)!=EOF){while(t--){scanf("%d%d%d", &m, &n, &d);for(i=1;i<=d;i++) scanf("%d%d", &v[i], &in[i]), v[i]/=1000;int tm;for(i=1;i<=n;i++){memset(dp, 0, sizeof(dp));tm=m/1000;for(j=1;j<=d;j++)for(k=v[j];k<=tm;k++)dp[k]=max(dp[k], dp[k-v[j]]+in[j]);m+=dp[tm];}printf("%d\n", m);}}return 0;}
