哇好火的dp啊.
开始根本想不出
这里如果顺着dp肯定是不行的,没办法记录钻头能力值
显然能力值的变化会影响后面收入
而具体影响就是:全部乘了1-0.01k或1+0.01c.
可以倒着dp(orz)
设f[i]表示初始能力为1 i~n可以搞到的最大收入.
然后如果是资源星球就\(f[i]=max(f[i+1],f[i+1]*(1-0.01k)+a[i])\)
维修星球是\(f[i]=max(f[i+1],f[i+1]*(1-0.01c)+b[i])\)
orz出题人 出的太绝了根本想不到!
// It is made by XZZ
// Fei Fan Ya Xi Lie~~~
#include<cstdio>
#include<algorithm>
using namespace std;
#define il inline
#define rg register
#define vd void
#define db long double
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
db f[100010];
int opt[100010],a[100010];
#define yyb 2333
int main(){
// freopen("2579.in","r",stdin);
// freopen("2579.out","w",stdout);
int n=gi(),beg;
db k=(1-0.01*gi()),c=(1+0.01*gi());
beg=gi();
for(rg int i=1;i<=n;++i)opt[i]=gi(),a[i]=gi()*yyb;
f[n+1]=0;
for(rg int i=n;i;--i){
if(opt[i]==1)f[i]=max(f[i+1],f[i+1]*k+a[i]);
else f[i]=max(f[i+1],f[i+1]*c-a[i]);
}
printf("%.2Lf",f[1]*beg/yyb);
return 0;
}