它……又是个DP
我……我讨厌DP!?
然后又是读入，显然用快读啊：（数据范围还是很大的）（习惯）
然后我们发现，不论是损耗值
维修值
，还是
采矿所得，维修花费
，都带着个p，因此我们可以把p提出来？
dp[i]表示第i个星球~第n个星球的最大赚取费用；
那么我们的解就是dp[1]；
考虑一下：
假设第i个是资源型，在之前已经求出dp[i+1]（代表从i+1开始选，1～i一概略过）的最大金钱数，那么dp[i]=max(dp[i+1]/*这个不选*/, a[i]+dp[i+1]*(1-0.01*k)/*第i个选了，加上金钱，当前钻头能力系数变为原来的(1-0.01*k)，那么后面的得到的最大金钱数也变为原来的(1-0.01*k)*/)
那么如果第i个是资源型也同理，如果我们选了它，那么对后面dp[i+1]，会使它的钻头能力变为原来的(1+0.01*c)倍，当然记得减去a[i]（把p已经提出来了qwq）
因此核心代码：
if(t[i]==1) dp[i]=max(dp[i+1],dp[i+1]*(1-0.01*k)+a[i]); else dp[i]=max(dp[i+1],dp[i+1]*(1+0.01*c)-a[i]);
最后不要忘记再将w乘回来（因为实际上p的改变都乘在dp数组中了，所以只需要乘原始值）
#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char last=' ',ch=getchar(); while(ch>'9'||ch<'0') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int n; double k,c,w; int x[100010],type[100010]; double f[100010]; int main(){ n=read(); scanf("%lf%lf%lf",&k,&c,&w); for(int i=1;i<=n;i++){ type[i]=read(); x[i]=read(); } for(int i=n;i>=1;i--){ if(type[i]==1) f[i]=max(f[i+1],f[i+1]*(1-0.01*k)+x[i]); else f[i]=max(f[i+1],f[i+1]*(1+0.01*c)-x[i]); } printf("%.2lf",f[1]*w); return 0; }
忍不住说某些s*jl
end-