简化边界的建议
查看原帖
简化边界的建议
554746
yiming564楼主2024/7/11 14:19

以第一篇题解为例,他提出的转移方程是

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})

其中有一个讨厌的 dpj−2dp_{j-2}

其实可以在读入任务区间 [l,r][l,r] 时将闭区间转化为开区间 (l,r)(l,r),并修改对状态的定义:dpidp_i 为第 ii 天不跑,前 i−1i-1 天任意的能量最大值。(其实也就是把 dpidp_i 修改为了开区间)

这样,讨厌的 dpj−2dp_{j-2} 就可以改为 dpjdp_j,没有了 −2-2 的问题,随便咋离散化都不会挂。

(我不知道有没有人和我一样在离散化 −2-2 这里卡死的)

2024/7/11 14:19
加载中...