//因为基金都是1000的倍数,所以把m和基金的花费。都缩小1000去进行背包求解,得到的解用未缩小的。总钱数去加,然后再缩小1000去求解下一年的。本金不是1000的整倍数也不会影响结果 #include<bits/stdc++.h> using namespace std; int T,amount,n,d,weight[12],profit[12],dp[1000002]; int main(){ scanf("%d",&T); while(T--){ memset(dp,0,sizeof(dp)); scanf("%d%d%d",&amount,&n,&d); for (int i=0; i<d; i++){ scanf("%d%d",&weight[i],&profit[i]); weight[i] /= 1000; } for (int i=0; i<n; i++){//枚举每一年 int t = amount/1000; for(int j=0;j<d;j++)for(int k=weight[j];k<=t;k++)dp[k]=max(dp[k],dp[k-weight[j]]+profit[j]);//枚举债券数;枚举背包容量(价值) amount += dp[t]; } printf("%d\n",amount); } return 0; }