team2012-F3-sol-0008

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：开始时有x钱y攻击力，有n个城市可以按顺序走
每个城市进入时可以用a[i]的钱提升1点攻击力，然后离开时每点攻击力可以获得b[i]的钱，问最后最多能拿多少钱。

解法：
这题是看了MJ学长的解题报告后写的，感觉这种方法很厉害而且比贪心好想一点，仰慕！！
MJ学长这种方法的具体做法是：
设 atk[i] 为进入第 i 个城市时有 1 点攻击力，那么最后能变成多少钱，
设 mon[i] 为进入第 i 个城市时有 1 块钱，那么最后能变成多少钱。

则有：
atk[n] = b[n] （进入第 n 个城市时有一点攻击，最后就是收获了 b[n] 块钱）
mon[n] = max{ (x / a[n]) * b[n] + (1 - x) | 0 <= x <= 1 } 
（设在这个城市花了 x 的钱提升攻击力，最后能拿多少，取一个最大值，
整理后可发现，只要看 x 前面的系数正负就可以了，正则 x 取 1，负则 x 取 0，所以只要判断一下就行）
对于其他的城市 i
atk[i] = atk[i+1] + b[i] * mon[i+1] （进入时的一点攻击力产生两部分收益：之后运用攻击力的收益和之后运用得到的 b[i] 块钱的收益）
mon[i] = max{ (x / a[i]) * atk[i+1] + [(x / a[i]) * b[i] + (1 - x)] * mon[i+1] | 0 <= x <= 1 }
（同样考虑花一块钱中的 x 元，也有两部分收益：买来的攻击力的收益；攻击力在离开时赚得的钱和这一块钱剩下的部分 1-x 在之后的收益,
同样只看 x 前的系数符号即可）
这样递推下来，最后的答案是 x * mon[1] + y * atk[1]
}}}
{{{
#include <iostream>
#include <iomanip>
using namespace std;

const int MAXN = 100005;
int n;
double x, y, a[MAXN], b[MAXN], mon[MAXN], atk[MAXN];

int main()
{
    while(cin>>n>>x>>y)
    {
        for(int i = 1; i <= n; i++)
            cin>>a[i]>>b[i];
        atk[n] = b[n];
        if(b[n] / a[n] > 1)
            mon[n] = b[n] / a[n];
        else
            mon[n] = 1;
        for(int i = n - 1; i >= 1; i--)
        {
            atk[i] = atk[i+1] + mon[i+1] * b[i];
            if(b[i] * mon[i+1] + atk[i+1] > a[i] * mon[i+1])
                mon[i] = (b[i] * mon[i+1] + atk[i+1]) / a[i];
            else
                mon[i] = mon[i+1];
        }
        cout<<setprecision(2)<<fixed<<(x * mon[1] + y * atk[1])<<endl;
    }
    return 0;
}
}}}

题意：开始时有x钱y攻击力，有n个城市可以按顺序走
每个城市进入时可以用a[i]的钱提升1点攻击力，然后离开时每点攻击力可以获得b[i]的钱，问最后最多能拿多少钱。
解法：
这题是看了MJ学长的解题报告后写的，感觉这种方法很厉害而且比贪心好想一点，仰慕！！
MJ学长这种方法的具体做法是：
设 atk[i] 为进入第 i 个城市时有 1 点攻击力，那么最后能变成多少钱，
设 mon[i] 为进入第 i 个城市时有 1 块钱，那么最后能变成多少钱。
则有：
atk[n] = b[n] （进入第 n 个城市时有一点攻击，最后就是收获了 b[n] 块钱）
mon[n] = max{ (x / a[n]) * b[n] + (1 - x) | 0 <= x <= 1 } 
（设在这个城市花了 x 的钱提升攻击力，最后能拿多少，取一个最大值，
整理后可发现，只要看 x 前面的系数正负就可以了，正则 x 取 1，负则 x 取 0，所以只要判断一下就行）
对于其他的城市 i
atk[i] = atk[i+1] + b[i] * mon[i+1] （进入时的一点攻击力产生两部分收益：之后运用攻击力的收益和之后运用得到的 b[i] 块钱的收益）
mon[i] = max{ (x / a[i]) * atk[i+1] + [(x / a[i]) * b[i] + (1 - x)] * mon[i+1] | 0 <= x <= 1 }
（同样考虑花一块钱中的 x 元，也有两部分收益：买来的攻击力的收益；攻击力在离开时赚得的钱和这一块钱剩下的部分 1-x 在之后的收益,
同样只看 x 前的系数符号即可）
这样递推下来，最后的答案是 x * mon[1] + y * atk[1]

#include <iostream>
#include <iomanip>
using namespace std;
const int MAXN = 100005;
int n;
double x, y, a[MAXN], b[MAXN], mon[MAXN], atk[MAXN];
int main()
{
    while(cin>>n>>x>>y)
    {
        for(int i = 1; i <= n; i++)
            cin>>a[i]>>b[i];
        atk[n] = b[n];
        if(b[n] / a[n] > 1)
            mon[n] = b[n] / a[n];
        else
            mon[n] = 1;
        for(int i = n - 1; i >= 1; i--)
        {
            atk[i] = atk[i+1] + mon[i+1] * b[i];
            if(b[i] * mon[i+1] + atk[i+1] > a[i] * mon[i+1])
                mon[i] = (b[i] * mon[i+1] + atk[i+1]) / a[i];
            else
                mon[i] = mon[i+1];
        }
        cout<<setprecision(2)<<fixed<<(x * mon[1] + y * atk[1])<<endl;
    }
    return 0;
}