edward-solution-0008

从 Trac 迁移的文章

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

原文章内容如下：

设mow[i]表示如果你在进入第i个城市之前，有1块钱，那么在之后最多能变成多少块钱[[BR]]
设apw[i]表示如果你在进入第i个城市之前，有1点攻击力，那么在之后最多会演化成多少块钱[[BR]]
然后转移什么的直接看代码吧...就像dp一样的思路[[BR]]
唯一需要说明的一点大概是：因为这个转换关系都是常数倍的关系，所以这些获利都可以分开考虑，最后叠加。
{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
int n, X, Y;
double a[N], b[N];
double mow[N], apw[N];

int main(){
#ifdef cwj
    freopen("in", "r", stdin);
#endif
    while (scanf("%d%d%d", &n, &X, &Y) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf", &a[i], &b[i]);
        }
        if (n == 0) {
            printf("%.2lf\n", X);
        } else {
            apw[n] = b[n];
            mow[n] = max(1.0 / a[n] * b[n], 1.0);
            for (int i = n - 1; i >= 0; i--) {
                apw[i] = apw[i + 1] + mow[i + 1] * b[i];
                mow[i] = max(1.0 / a[i] * b[i] * mow[i + 1] + apw[i + 1] * 1.0 / a[i], mow[i + 1]);
            }
            printf("%.2lf\n", X * mow[1] + Y * apw[1]);
        }
    }
}
}}}

设mow[i]表示如果你在进入第i个城市之前，有1块钱，那么在之后最多能变成多少块钱

设apw[i]表示如果你在进入第i个城市之前，有1点攻击力，那么在之后最多会演化成多少块钱

然后转移什么的直接看代码吧...就像dp一样的思路

唯一需要说明的一点大概是：因为这个转换关系都是常数倍的关系，所以这些获利都可以分开考虑，最后叠加。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
int n, X, Y;
double a[N], b[N];
double mow[N], apw[N];
int main(){
#ifdef cwj
    freopen("in", "r", stdin);
#endif
    while (scanf("%d%d%d", &n, &X, &Y) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf", &a[i], &b[i]);
        }
        if (n == 0) {
            printf("%.2lf\n", X);
        } else {
            apw[n] = b[n];
            mow[n] = max(1.0 / a[n] * b[n], 1.0);
            for (int i = n - 1; i >= 0; i--) {
                apw[i] = apw[i + 1] + mow[i + 1] * b[i];
                mow[i] = max(1.0 / a[i] * b[i] * mow[i + 1] + apw[i + 1] * 1.0 / a[i], mow[i + 1]);
            }
            printf("%.2lf\n", X * mow[1] + Y * apw[1]);
        }
    }
}