Lemonade Trade

题目描述：

你有一升粉色饮料，想换取蓝色饮料

有n个商人，每个商人可以将1升b饮料换成p升a饮料，p是汇率，只能从1到n顺次访问商人，到每个商人的地方可以选择换或不换，换的量也可以任意，不可以回头

问最多能获得多少蓝色的饮料，如果能换的蓝色饮料大于10升，则输出10即可

思路：

一眼DP

设dp[i]表示能换出i的饮料的体积的最大值

则对于一个商人，假设1升a可以换p升b，dp[b] = max(dp[b], dp[a] * p)

但是如果都是大于1的汇率，很快就会乘爆，所以我们可以考虑用用log来将乘法降级为加法

dp[b] = max(dp[b], dp[a] + log10(p))

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MAX 300050
int n;
double p;
string s, t;
map<string, double>dp;

void work()
{
    cin >> n;
    dp["pink"] = 0.0;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s >> t >> p;
        if(dp.count(t))
        {
            if(!dp.count(s))dp[s] = dp[t] + log10(p);
            else dp[s] = max(dp[s], dp[t] + log10(p));
        }
    }
    if(dp["blue"] == 0)printf("0.00000000\n");
    else if(dp["blue"] - 1 >= 1e-8)printf("10.00000000\n");
    else printf("%.8lf\n", pow(10.0, dp["blue"]));

}

int main()
{
    work();
    return 0;
}