完全背包 poj 2063 Investment
#include <iostream>#include <cstdio>#include <cstring>using namespace std;int c[20];int I[20];int dp[50050];int main(){ int rest,capital,t,year,bnum; scanf("%d",&t); while(t--) { rest=0; capital=0; year=0; bnum=0; scanf("%d%d",&capital,&year); scanf("%d",&bnum); for(int i=0;i<bnum;i++) { scanf("%d%d",&c[i],&I[i]); c[i]/=1000; } for(int i=0;i<year;i++) { memset(dp,0,sizeof(dp)); rest=capital%1000; capital=capital/1000; for(int j=0;j<bnum;j++) { for(int k=c[j];k<=capital;k++) { dp[k]=max(dp[k],dp[k-c[j]]+I[j]); } } //cout<<dp[capital]<<' '<<rest<<endl; //capital=rest+dp[capital]+capital*1000; int sum=dp[capital]; capital=rest+sum+capital*1000; //cout<<capital<<endl; } cout<<capital<<endl; } return 0;}?