以第一篇题解为例,他提出的转移方程是
dpi=max(dpi,dpj−2+(i−j+1)d+wj,i)dp_i=\max(dp_i,dp_{j-2}+(i-j+1)d+w_{j,i})dpi=max(dpi,dpj−2+(i−j+1)d+wj,i)
其中有一个讨厌的 dpj−2dp_{j-2}dpj−2
其实可以在读入任务区间 [l,r][l,r][l,r] 时将闭区间转化为开区间 (l,r)(l,r)(l,r),并修改对状态的定义:dpidp_idpi 为第 iii 天不跑,前 i−1i-1i−1 天任意的能量最大值。(其实也就是把 dpidp_idpi 修改为了开区间)
这样,讨厌的 dpj−2dp_{j-2}dpj−2 就可以改为 dpjdp_jdpj,没有了 −2-2−2 的问题,随便咋离散化都不会挂。
(我不知道有没有人和我一样在离散化 −2-2−2 这里卡死的)