首页 > 代码库 > [POJ 2063] Investment (动态规划)
[POJ 2063] Investment (动态规划)
题目链接：http://poj.org/problem?id=2063
题意：银行每年提供d种债券，每种债券需要付出p[i]块钱，然后一年的收入是v[i]，到期后我们把本金+收入取出来作为下一年度本金继续购买债券。
问你起始本金为n元，m年后你手里最多能有多少钱。
其实这题不难。。我却想了一会。。
因为题目保证了p[i]是1000的倍数，所以我们可以把本金和p[i]都先除以1000，然后算出每年可能获得的最大收入，然后加到本金当中，在暴力枚举m年就行了。
设计状态dp[j]代表我花了不超过j元钱，得到的最大的收入。
按照完全背包问题，dp[j] = max(dp[j],dp[j-p[i]]+v[i]);
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int T,n,d,m;12 int dp[100000];13 int v[11],p[11];14 const int INF = 999999999;15 16 int main(){17 scanf("%d",&T);18 while( T-- ){19 scanf("%d%d",&n,&m);20 scanf("%d",&d);21 for(int i=1;i<=d;i++){22 scanf("%d%d",&p[i],&v[i]);23 p[i] /= 1000;24 }25 int s = n, st = n/1000;26 for(int k=1;k<=m;k++){27 memset(dp,0,sizeof(dp));28 for(int i=1;i<=d;i++){29 for(int j=p[i];j<=st;j++){30 dp[j] = max(dp[j],dp[j-p[i]]+v[i]);31 }32 }33 // printf("k=%d and dp[st] = %d\n",k,dp[st]);34 s += dp[st];35 st = s / 1000;36 }37 printf("%d\n",s);38 }39 return 0;40 }41 42 /*43 144 10000 445 246 4000 40047 3000 25048 */
[POJ 2063] Investment (动态规划)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。