110000 424000 4003000 250 Sample Output14050 SourceNWERC2004 题意:给出初始资金,还有年数,然后给出每个物品的购买价格与每年获得的利益,每个物品可选多次,要求在给出的年份后所能得到的最大本利之和。思路:由于给出的资金过大,循环会超时,题目说了本金与物品的购买价格都是1000的倍数,所以我们可以将他们都除以1000来进行压缩,然后就是一道完全背包模板题了。代码:#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int N=20;const int M=500000;int dp[M];struct node{ int a,b;}str[N];int main(){ int T; scanf("%d",&T); while(T--) { int a,t; scanf("%d%d",&a,&t); int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&str[i].a,&str[i].b); str[i].a/=1000; } for(int i=1;i<=t;i++) { int ans=a/1000; memset(dp,0,sizeof(dp)); for(int j=0;j<n;j++) for(int k=str[j].a;k<=ans;k++) dp[k]=max(dp[k],dp[k-str[j].a]+str[j].b); a+=dp[ans]; } printf("%d/n",a); }}
新闻热点
疑难解答