原题连接 https://www.luogu.org/problemnew/show/P1412
此题作为今天校内测试的T3，由于我太蒟蒻没有想到要用 DP做，打个O（2n）的搜索潇洒暴零QwQ~
听了 water_lift 的讲解并看了不下 10 分钟的题解后，我终于明白了这个题。
其实这个题 DP 还是很容易看出来的：对于每个星球，我们可以选或不选，这不就是标准的 DP 转移方程嘛？
考虑后效性
钻头初始值为 w，随着经过的星球它的能力值也在不断改变，也就是说前面的情况会影响到后面的情况，有后效性！怎么办？
既然从前往后会影响后面的，那么我们从后往前不就谁也影响不到了嘛？（真是个小机灵鬼~
考虑到我们采资源时得到的金钱为：a [ i ] * p，钻头的能力变为：（1 - 0.01k）* p；修复钻头所耗费的金钱为：b [ i ] * p，钻头的能力变为：（1 + 0.01c）* p；我们发现我们每一步变换都和 p 有关，这搞得我们很烦，所以我们干脆把 p 提出来，再将最终答案乘上 p （一开始的初始值 p = w）是不会影响我们的答案的，反而会简化计算哦。
将 p 提出来后，问题就简化成：采资源时得到的金钱为：a [ i ]，钻头的能力变为：1 - 0.01k；修复钻头所耗费的金钱为：b [ i ]，钻头的能力变为：1 + 0.01c；
考虑到钻头能力值得每一步变换都会对以后星球的活动造成影响，我们先以资源型星球为例：
假设我们已经在一个资源型星球采集完资源了，这时候我们得到的金钱就是：a [ i ] * p，钻头能力变为：p' = p *（1 - 0.01k）；那么对于以后星球的任何一种活动，我们都要用这个当前钻头能力值 p' 去计算活动的贡献的；假设我们又到了一个资源型星球来采集资源，我们得到的金钱就是： a [ j ] * p' = a [ j ] * p *（1 - 0.01k），但如果我们不在上一个 i 星球采集的话（钻头没有损耗），那么我们当前的这个 j 星球得到的金钱应该就是： a [ j ] * p，对比于上一个式子，我们可以发现：在某一个资源型星球采集完资源后，对于后面采集资源的影响就是：资源变成了（1 - 0.01k）倍；
同理对于在维修型星球修钻头后，对于以后的采集金钱的活动采集到的金钱都会变成（1 + 0.01c）倍；
这就是状态转移方程！
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n; double k,c,w; //k是损耗 //c是修复 struct planet { int type,x; }a[100001]; double f[100001]; int main() { scanf("%d%lf%lf%lf",&n,&k,&c,&w); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].type,&a[i].x); for(int i=n;i>=1;i--) { if(a[i].type==1) //资源型星球对后面活动的影响 f[i]=max(f[i+1],a[i].x+f[i+1]*(1-0.01*k)); //f[i+1]:在第i个星球上啥也不干,那么金钱和后一个的金钱是一样的 //f[i+1]*(1-0.01*k)就是对后面的采集金钱的影响,a[i].x就是本星球采到的金钱,注意这里是提出p以后的 else f[i]=max(f[i+1],-a[i].x+f[i+1]*(1+0.01*c)); //维修型,转移方程的解释与上面的解释同理,这里的a[i].x其实就是题目的b[i],为了方便用一个变量表示了 } printf("%.2lf",w*f[1]); //两位小数 return 0; }