UOJ Logo bright_sun的博客

博客

NOIP2016T3的神奇感触

2016-11-19 13:38:40 By bright_sun

这是退役狗的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。

NOI2013 小Q的修炼 题解

2016-05-20 10:20:40 By bright_sun
bright_sun Avatar