关于这个题的一个神必做法
查看原帖
关于这个题的一个神必做法
304550
black_trees楼主2022/4/15 16:10

就只考虑 O(n2)\text{O}(n^2) 的DP,

正常人写的都是考虑让每次分段时机器启动对后面造成的贡献提前计算,然后因为前面的任务在除去启动时间之后就是总共花费时间就是 sumtisumt_i

然后会写出一个方程:

dpi=min0j<i{dpj+sumti×(sumcisumcj)+S×(sumcnsumcj)}dp_{i} = \min\limits_{0\le j < i}\{dp_j + sumt_i\times(sumc_i-sumc_j) + S \times (sumc_n-sumc_j)\}

这个做法是可以斜率优化的。

但是我今天重新做的时候写出了另外一个神必的方程:

直接考虑把当前这批任务造成的贡献也直接提前计算:

然后得到:

dpi=min0j<i{dpj+(S+sumt[i]sumt[j])×(sumc[n]sumc[j])}dp_{i} = \min\limits_{0\le j < i}\{dp_j + (S + sumt[i] - sumt[j]) \times (sumc[n] - sumc[j])\}

这个方程也是对的(AC记录),但是我看了大半天,一直觉得这东西没法斜率优化。

所以想问问,这个方程有没有办法斜率优化啊?

假设不行的话,那如果我考场上遇到这样的情况,该怎么样才能想到另外一个可以斜率优化的方程呢?

2022/4/15 16:10
加载中...