这是退役狗的NOIP模拟赛♂感触，大神可以直接关掉了。
刚开始看到这道题，很自然地想到设 $f[i][j][k(0/1)]$ 表示“到第 $i$ 节课，用了 $j$ 个名额，$i$ 是否申请名额”的期望。但这样是无法直接转移的，因为名额不一定成功。于是我“灵机一动”，把 $k$ 的意义变换成“此时处在的位置”。然后我再倒着dp来尝试表达出 $f[i][j][k]$。①决策“选下一个名额”，那么可以用 $f[i+1][j-1][1]$ 加距离再乘上 $p[i+1]$（选的下一个成功了），以及 $f[i+1][j-1][0]$ 加距离再乘上 $1-p[i+1]$ 转移过来；②决策“不选下一个名额”，就直接从 $f[i+1][j][0]$ 加距离转移过来。
这方法看上去很带劲啊！在试场上我实现了一下只过了小样例，比大样例小一点点。>< 我以为是退役太久代码能力等于零了，就一直在肉眼查错。结果GG了。
出考场后发现本题的普遍做法是：直接正着DP， $k$ 仍然表示 $i$ 是否申请了名额。转移的时候再枚举 $i+1$ 的 $k'$ ，然后根据期望的线性性，把 $i~i+1$ 这条边的贡献统计进去。比如，如果$k=0，k'=1$，那么 $i$ 处一定在 $i+1$ 处有两种可能，用 $p[i+1]$ 和 $1-p[i+1]$ 分别乘上最短路转移即可。
这种方法显然是对的，而且十分好想。于是我就在思考——我的方法错在哪里（还是写挂了），以及为何我没有想到这样的方法。
我现在得到了一种可能的原因。本题有个很重要的要求是，“先选出所有点再计算期望，并求出最大值”。这个问题看上去很显然（事实上我在想DP方程的时候根本没有管他），实际上很致命QAQ。仔细观察我的DP方程，可能“ $i$ 之后的申请是否通过的情况，会干预到本次的决策”。
得出结论：自己果然不适合搞OI QAQ。
鄂公网安备 42010202000505 号