【JZOJ 5377】【NOIP2017提高A组模拟9.19】开拓

Description

Solution

很显然，这题有O(n3)的DP，
考虑一下怎么优化，发现瓶颈在于没法表示钻头的能力值，
我们发现，当前钻头的能力值的改变，对于后面的影响是乘上一个数，而且这个数很好算，
那么就是说，我们倒过来DP，设当前的w值为1，即可从后面转移了，

复杂度:O(n)

Code

#include <cstdio>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
typedef double db;
const int N=100500;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
    for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
    if(ch=='-')w=-1,ch=getchar();
    for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
db m1,m2,m0;
int a[N],ak[N];
db f[N];
int main()
{
    freopen("exploit.in","r",stdin);
    freopen("exploit.out","w",stdout);
    int q,w;
    read(n),m1=1-0.01*read(q),m2=1+0.01*read(q),m0=read(q);
    fo(i,1,n)read(ak[i]),read(a[i]);
    f[n+1]=0;
    fod(i,n,1)
    {
        f[i]=f[i+1];
        if(ak[i]==1)
        {
            f[i]=max(f[i],a[i]+m1*f[i+1]);
        }else f[i]=max(f[i],m2*f[i+1]-a[i]);
    }
    printf("%.2lf\n",f[1]*m0);
    return 0;
}