自动搬运

查看原文

来自洛谷，原作者为

	bigclever 要被劝退力（悲

搬运于2025-08-24 21:40:49，当前版本为作者最后更新于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;
}