赚钱计划

1. 题目描述

小 Q 决定在新的一年里赚大钱，小 P给 TA 推荐了理财。小 Q 在今年初 (非闰年) 有100000元 (好有钱啊),有N个理财产品，每个理财产品用三个参数描述：购买时间，投资天数，年利息率。每个时刻小Q 只能拥有最多一件产品，求一年后最多可以获得多少钱。

输入格式

第1行，一个整数。 接下来行，每行为 3 个空格隔开的字符串 A 表示发行时间，格式为 MMDD; B 是一个整数，为投资天数，范围[10,300]; C 为最多 2 位小数，代表百分之几的年利息，范围[3,30];

输出格式

一个数，为年底最多可以获得的连本带利的资金数目，保留两位有效小数。

样例输入 #1

3 0101 100 4.5 0201 30 5 0402 50 7.8

样例输出 #1

101483.84

2. 分析

先建一个动规数组，每一项表示每天的最大收益。一年最多只有 365天，所以我们可以跑一个 365次的循环，每次判断每个理财产品是否到期，再用银行算利息的方法算出收益。然后就是他按照月份读入，我么可以先预处理一个数组打出一个月份的表，之后借助月份数组把哪个月的第几天转化成为一年中的第几天。

3. 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int month[13]={0,0,31,59,90,120,151,181,212,243,273,304,334};//月份数组
int n,x,a[1000001],b[1000001];
double c[1000001],f[1000001];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>b[i]>>c[i];
        a[i]=month[x/100]+x%100;//天数处理
    }
    f[1]=100000;//初始化
    for(int i=2;i<=366;i++){
        f[i]=f[i-1];
        for(int j=1;j<=n;j++){
            if(a[j]+b[j]==i){//到期了
                f[i]=max(f[a[j]]*(1+(c[j]/100)/365*b[j]),f[i]);//状态转移方程
            }
        }
    }
    printf("%.2lf",f[366]);//输出最后一天最大的收益
    return 0;
}