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。

评论

WrongAnswer
果然今年NOIP画风和以往都很不一样了。试卷板式更改(吓得我以为Day2有提交答案题),测试点变多(今年才有的25个点的题),每题都有测试点详细情况(包括第1题),难度增大(D1T2就已经难成这样了)。 T3一开始也想到状态记位置是 $c_i$ 还是 $d_i$,后来看题目,发现不能根据之前是否成功来更改决策,就有一种这样做是错的感觉,后来写了大众做法,过了样例<del>结果对拍WA了也不知道为什么来不及调了感觉要爆0了</del>。 听说T3大样例弱,好虚啊。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。