首页 > 代码库 > hdu 1963 Investment 解题报告

hdu 1963 Investment 解题报告

2024-07-15 11:09:43   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1963

题目意思：有 本金 money，还有一些股票的种类，第 i 种股票买入需要 value[i] 这么多钱，相应会有一定的利息interest[i]，问经过若干年 year 后，每年都以最优的方案投资，总的资金有多少？

      完全背包题，不过要看清楚 这句话：The value of a bond is always a multiple of $1 000，否则TLE了

     

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 1e6 + 5; 7  8 typedef long long ll; 9 int value[maxn], interest[maxn];10 ll dp[maxn], ans, money, tolmoney;11 12 int main()13 {14     int kind, tcase, year;15     while (scanf("%d", &tcase) != EOF)16     {17         while (tcase--)18         {19             scanf("%lld%d", &money, &year);20             scanf("%d", &kind);21             for (int i = 0; i < kind; i++)22             {23                 scanf("%d%d", &value[i], &interest[i]);24                 value[i] /= 1000;25             }26             memset(dp, 0, sizeof(dp));27             ans = 0, tolmoney = money;28             for (int j = 0; j < year; j++)29             {30                 if (j != 0)31                     money = tolmoney;32                 money /= 1000;33                 for (int i = 0; i < kind; i++)34                 {35                     for (int k = value[i]; k <= money; k++)36                     {37                         dp[k] = max(dp[k], dp[k-value[i]] + interest[i]);38                         ans = max(dp[k], ans);39                     }40                 }41                 tolmoney += ans;42             }43             printf("%lld\n", tolmoney);44         }45     }46     return 0;47 }

 


联系
我们