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

Description

Input

Output

Sample Input

5 50 50 10
1 10
1 20
2 10
2 20
1 30

Sample Output

375.00

Data Constraint

Solution

• 本题最大的瓶颈在于“当前钻头能力”，我们尝试不储存“当前钻头能力”。

• F[i] 表示前 i 个星球的最优收入。但这很明显是不行的，因为当前钻头能力会影响到后面的过程。

• 不严谨的说，当前钻头能力具有“后效性”。

• 但是这个当前钻头能力对后程的影响无非就是乘上一个数值。

• 就好像初始钻头能力是 w ，实际上你可以按 1 来做，最后再把 ans 乘上 w 。

• 正难则反 ，F[i] 表示第 i——n 个星球的最优收入，且假设从第 i 个星球开始时钻头能力是 1 。

• 转移过程就变得简单：

• 如果在第 i 个星球开采，那么第 i——n 个星球的初始钻头能力就是 1∗(1−0.01∗k) 。

• 换句话说，就是：F[i+1]∗(1−0.01k) 。所以：

  F[i]=Max{F[i+1],F[i+1]∗(1−0.01k)+a[i]}

• 对于维护型星球，大同小异，就系数和代价的正负而已。

• 实际处理时数组也不用，用变量存储即可，时间复杂度 O(N) 。

Code

#include<cstdio>
using namespace std;
const int N=100001;
double ans;
int a[N];
bool b[N];
inline int read()
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline double max(double x,double y)
{
    return x>y?x:y;
}
int main()
{
    int n=read();
    double k=read(),c=read(),w=read();
    k=1-0.01*k,c=1+0.01*c;
    for(int i=1;i<=n;i++) b[i]=read()==1,a[i]=read();
    for(int i=n;i;i--) ans=max(ans,b[i]?ans*k+a[i]:ans*c-a[i]);
    printf("%.2lf",ans*w);
    return 0;
}