P2721题解

bigclever · 2023-05-11 13:19:41 · 题解

思路：

本题需要使用动态规划实现。

设 dp_i 表示第 i 天的最大收益，我们先让 dp_i=dp_{i-1}，即把上一天的最大收益先转移过来，然后枚举每一个理财产品，如果它刚好是第 i 天到期，那么 dp_i 就取该理财产品的收益和 dp_i 之间的最大值。因为是求一年后的最大收益，所以答案即为 dp_{366}。

当然还有几个需要注意的问题：

1. 题目读入的时间格式为 MMDD，所以需要先算出到第 i 月已经过去了多少天，再加上天数才是真正的购买时间。
2. 理财产品收益的计算方式：设该产品的购买时间为 x，投资天数为 y，年利息率为 z，那么该产品收益为 dp_x \times [1+(z \div 100) \div 365] \times y。

   Code:

   #include<bits/stdc++.h>
   using namespace std;
   int st[10005],day[10005];
   double lx[10005],dp[367];
   const int mon[]={0,0,31,59,90,120,151,181,212,243,273,304,334};
   int main(){
       int n; cin>>n;
       for(int i=1,x;i<=n;i++){
           cin>>x>>day[i]>>lx[i];
           st[i]=mon[x/100]+x%100;//转换为真正的购买时间
       }
       dp[1]=100000;//第一天最大收益为100000
       for(int i=2;i<367;i++){
           dp[i]=dp[i-1];
           for(int j=1;j<=n;j++)
               if(st[j]+day[j]==i)//如果该理财产品刚好是第i天到期
                   dp[i]=max(dp[i],dp[st[j]]*(1+(lx[j]/100)/365*day[j]));//取最大收益
       }
       printf("%.2lf",dp[366]);
       return 0;
   }