RT。虽然讨论区里已经有相关讨论了,不过含金量似乎集中在某几个帖子而且原因似乎不是特别详细
这里稍微总结一下为什么会 88 pts:
如果你设 f[i][j][k] 表示当前到 i、剩 j 次机会,当前在教室 k,那么 88pts 是预料之中的,因为这种状态设计是错误的。题目中有说,一开始就必须决策好是否申请。也就是说你不能临时根据你上一次的决策是否成功来决定下一次是否申请。
简而言之就是:每次决策是不应该知道上一次决策是否成功的。也就是不知道上一次决策是在哪个教室。
如果设 f[i][j][k],k 表示上一次决策是否成功,没有本质区别。照样 88 pts(本人即为此情况)
状态设计中不应该包含与上一次决策有关的信息。无论是上一次的教师位置还是上一次的决策成功与否。
应当做的是设 k 为在第 i 个课程时是否申请。然后转移时分两种情况计算第 i+1 个课程是否申请。两种情况取最小值即可。
有误恳请指正