个人认为第一篇题解有误
查看原帖
个人认为第一篇题解有误
727076
hexz01楼主2024/7/5 11:27

对于第一遍题解所说的:

这道题 kk 前几篇题解必须正序枚举的原因并不是什么要用 j−kj−k 更新答案,而是因为正序枚举 kk 是从 00 开始的,而这道题的状态转移必须要先将 k=0k=0 的状态转移过来才能成立。也就是说,这只是个巧合,jj 的枚举要倒序没错,但 kk 的枚举必须正序简直就是无稽之谈。要想避免这一情况,只需提前转移一下 k=0k=0 的情况即可。

个人认为本题的 kk 应当先算 k=0k=0,再算 k=1~jk=1~j。而 k=1~jk=1~j 的遍历顺序两种都可以,先算 k=0k=0 是因为需要用到 fu,jf_{u,j},也就是正在更新的那个,此时如果在后面更新 k=0k=0 会重复计算 fu,jf_{u,j}。

2024/7/5 11:27
加载中...