如果你 WA on 16,17,18

P1850 [NOIP 2016 提高组] 换教室

KeiTendou @ 2022-09-19 23:30:19

RT。虽然讨论区里已经有相关讨论了，不过含金量似乎集中在某几个帖子而且原因似乎不是特别详细

这里稍微总结一下为什么会 88 pts：

如果你设 f[i][j][k] 表示当前到 i、剩 j 次机会，当前在教室 k，那么 88pts 是预料之中的，因为这种状态设计是错误的。题目中有说，一开始就必须决策好是否申请。也就是说你不能临时根据你上一次的决策是否成功来决定下一次是否申请。

简而言之就是：每次决策是不应该知道上一次决策是否成功的。也就是不知道上一次决策是在哪个教室。

如果设 f[i][j][k]，k 表示上一次决策是否成功，没有本质区别。照样 88 pts（本人即为此情况）

状态设计中不应该包含与上一次决策有关的信息。无论是上一次的教师位置还是上一次的决策成功与否。

应当做的是设 k 为在第 i 个课程时是否申请。然后转移时分两种情况计算第 i+1 个课程是否申请。两种情况取最小值即可。

有误恳请指正

by jingkongwanglimiaoa @ 2022-10-05 20:26:43

省流：f[i][j][0]与f[i][j][1]可能并不由同一种情况转移而来，在计算下一个时刻时显然我们不能将两种不同情况的权值算在一起

by _l_l_ @ 2022-10-12 17:18:28

啊 van 分感谢

by Calvin0221 @ 2022-10-14 22:19:16

啊！逝坟干屑~

by kabout @ 2023-03-25 19:21:08

顶上去。

感觉这一次全部申请完确实是一个巨坑，如果不是一次性申请完的话这个可能是对的。

by kabout @ 2023-03-25 19:59:55

感觉这样设置状态的本质错误就是上一次选择交换还是不交换会混在一起，求得每个位置的贪心最小值。

by 岂非 @ 2023-05-15 20:40:47

拜谢ff0

by tNuxvs5t @ 2023-05-18 13:33:45

orz

by mediocre_ @ 2026-07-26 15:13:31

考古

by CloudResting @ 2026-09-05 14:31:07

%%%