首页 > 代码库 > [POJ 2063] Investment (动态规划)

[POJ 2063] Investment (动态规划)

2024-07-29 06:39:12   220人阅读

题目链接：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 (动态规划)


联系
我们