题解 P1912 【[NOI2009]诗人小G】

AThousandSuns · 2019-01-24 14:26:24 · 题解

upd on 2023.9.2 经评论区 @bingxin 提醒代码过不了样例，发现是添加注释时多删了如下一行导致的：

if(calc(i,n)>calc(q[r],n)) continue;

这会导致状态 i 在完全不优于目前队尾的情况下（可以发现 i 无法成为任何一个位置的最优决策），进行错误的决策替换。

另外一种修改方法如评论区 @20200131wyz 所提（此处为未认真对待每一条评论深感愧疚），将二分边界改为 n+1，这也起到了判断 i 究竟是否优于队尾的作用。修改后的版本采用这种方法。

另外再修改了一下排版以及部分概念。

什么是决策单调性优化 dp？

形如 dp_i=\min/\max(dp_j+f(j,i)) 这类的式子，令 t_i 为使得 dp_i 取到 \min/\max 的 j，（其实 t_i 就叫最优决策）若 t_i 具有单调性，则这个 dp 式子就满足决策单调性。

具体如何判断？

令 f_j(i) 为用 j 转移时 dp_i 的值（即 dp_j+f(j,i)）。

若对于任意 j_1<j_2，f_{j_1}(i) 和 f_{j_2}(i) 的函数图像至多有一个交点，在这个交点之前是 f_{j_1}(i) 更小，在这个交点后是 f_{j_2}(i) 更小，那么这个问题就满足决策单调性。

因为交点之前的 i 的决策都是 j_1，交点后的决策都是 j_2。正好满足决策单调性。

（其实如果反之，在交点前都是 j_2 更优而交点后都是 j_1 更优，是一种不同的决策单调性问题，因与本题无关此处略去。）

决策单调性的优化方法大致有决策栈，决策队列和分治。这题就是用决策队列优化。

决策队列具体是这样做的：

队列维护决策三元组 (p,l,r) 表示目前看来 t_l,t_{l+1}\dots t_r 都是 p。一般来说一开始队列里只有三元组 (0,1,n)。

每次计算 dp_i 时，就先把队列中无用的三元组弹出（r<i），并把新的队首的 l 设为 i。此时 i 在队首，所以 i 的决策就是队首的 p。用 dp_p 更新 dp_i。

接下来从队尾开始扫，如果用 i 来更新队尾的 l 比队尾的 p 更新队尾的 l 更优，说明队尾的决策应该比 p 更大（因为我们从小到大枚举 i），那么根据决策单调性，整个三元组中的决策都比 p 大。于是便可以弹出队尾。

到最后用 i 来更新队尾的 l 没有队尾的 p 更新队尾的 l 优。那么我们就要找出决策变为 i 的分界点。由于决策具有单调性，我们可以二分。二分边界就是队尾三元组的 l 和 n（为什么不是 r？因为可能这整个三元组都满足原来的决策，此时二分却会把最后一个元素拆走）。

二分出分界点 x 后，队尾三元组的 r 应改为 x-1（之后的决策都要变）。队尾再新加入一个三元组 (i,x,n)，表示 x 到 n 的决策都可以改为更优的 i。

至此算法结束。

因为每一个 i 都会至多添加一个三元组，对一个三元组进行二分，又因为一个三元组至多被删除一次，所以复杂度为 O(n\log n)。

回到原题。