【搜索】牛客网-Wannafly挑战赛12-A 银行存款

题目链接：https://www.nowcoder.com/acm/contest/79/A

　　

　　第一眼看到这个题的反应是使用贪心来写，优先存5年其次3年、2年、1年。但是程序重写两遍都是样例都对不上（不得不吐槽一下牛客网这个描述，太烂了）。花了40分钟才读懂这道题公式的意思~~~

　　假设你手里有M元  存i年，利息为ri

　　那么你到期以后手中的金额应该为Mx(1+ri)^i；   ---   ①

　　假设再存j年，利息为rj 

　　那么到期以后你手中的金额应该为①x(1+rj)^j；

（这样描述一通好像更不容易明白了···   没懂就看代码吧）

　　在调试完以后发现提交上去只能通过75%的数据，找了很久以后发现自己一开始便想错了

　　假如存6年，（5年+1年）未必比（3年+3年）或者（2年+2年+2年）的收益要高

　　可以用这组数据测试下 ： 6 0.0400 0.0471 0.0472 0.0473

　　因为这道题的数据量很小，所以无需优化，直接暴力搜索是不会超时的

　　但是如果数据量大的话，就要用动态规划来写了

　　　　代码：

#include <bits/stdc++.h>

using namespace std;

double MAX = 0.0;   // 存储答案
int a[5] = {0,1,2,3,5};   // 存的年数
double b[5];   // 年利率

// n:还可以存入n年   temp:目前的这种方案可获得的收益
void dfs(int n,double temp)
{
    // 当不能再存入时进行比较，是否当前方案比之前的方案收益更大
    // 若比之前的方案收益更大则更新MAX的值
    if(n == 0)
    {
        if(MAX < temp)
        {
            // 更新MAX的值
            MAX = temp;
            return ;
        }
    }
    else
    {
        for(int i = 4;i >= 1;i--)
        {
            // 如果n-a[i] >= 0说明可以进行年数为a[i]的存款行为
            if((n-a[i]) >= 0)
            {
                temp *= pow(1.0+b[i],a[i]);
                dfs(n-a[i],temp);   // 尝试继续存入
                // 尝试结束，回到尝试前的状态
                temp /= pow(1.0+b[i],a[i]);
            }
        }
    }
    return ;
}

int main()
{
    int n;    
    scanf("%d",&n);   // 读入存的总年数n
    // 读入1、2、3、5年的年利率
    scanf("%lf %lf %lf %lf",&b[1],&b[2],&b[3],&b[4]);
    // 暴力搜索
    dfs(n,1.0);
    // 输出
    printf("%.5f
",MAX);
    return 0;
}