关于DP的优化

学术版

ningago @ 2022-06-16 14:21:35

RT。原题是https://darkbzoj.cc/problem/4658

dp式子是：

dp_i = \max_{0\leq j < i }\{dp_j-a\left\lfloor\dfrac{t_i-t_j}{d}\right\rfloor\} + b_i

很明显这是个 n^2 算法，然后我思考这个式子的决策点，在一顿打表之后发现这玩意的决策点要么在之前算过的最大的决策点之后（即决策单调，但不完全是），要么在最大的决策点之前，但差值很小。

于是我估了个 200，就有了这里的代码。

结果过了……

求大佬hack

by Prean @ 2022-06-16 14:32:43

@ningago 将ti对d取模相同的节点分到同一组

同组之间使用单调队列转移，不同组也可以使用单调队列转移

应该可以做到O(n)

hack的话挺简单，在两个位置之间塞>200个收益为负数的点，然后就会寄了

by ningago @ 2022-06-16 14:34:23

@Prean %%%

by Prean @ 2022-06-16 14:37:15

哦不对

假设ti%d是一种颜色，应该把所有颜色的最优决策点塞进一个堆，取最大值和次大值判断即可

nlogn

by ningago @ 2022-06-16 14:50:37

@jijidawang

正解就是线段树优化

（但我只是想知道为什么这个胡搞做法过了

by Prean @ 2022-06-16 20:54:28

@ningago 很简单就是数据水

bzoj上面数据水的题多了去了（

|