决策单调性优化DP
以前没学会, 现在感觉好简单啊. 可能是冯佬讲得太好了.
首先要证明打表看出决策单调性.
然后是做法:
假设我们正在做$i = 6$位置, 现在$i$后面的决策是这样的:
111113333344444555555
可以发现, 决策相同的点是一段连续的区间.
用队列维护$i$位置之后的区间. 队列中的元素是个三元组$(l, r, p)$, 表示$[l, r]$这段区间内的决策是$p$.
做完$i$后, 自然要考虑$i$能改变哪些位置的最优决策, 比如可能变成这样:
111113333344444555555
111113333344444555666
或者这样
111113333344444555555
111113336666666666666
当然也可能这样
111113333344444555555
666666666666666666666
注意到, 可以被改变的区间一定是一段后缀.
所以可以二分一下.
具体来说, 我们先需要处理队尾的元素. 如果整个区间都是从$i$转移更优, 那么直接出队即可. 判断是否整个区间都是最优的也很简单, 只需判断这个区间的左端点$l$即可(因为是一段后缀).
如果某个区间的$l$不是从$i$转移更优, 而是他原来的转移点更优, 则证明这个区间内存在分界线, 最后的决策应该长这样:
ppppppppiiii
所以我们再二分这个区间, 找到第一个$i$, 设位置为$l’$, 修改队尾区间的$r = l’ - 1$, 然后push一个$(l’, n, i)$进去, 就完成了.
当然如果没有任何点从$i$转移更优就不用push了.
在取决策点的时候, 也需要二分$i$在队列中的哪个区间里.
就, 写完了…
int tail = 0;
que[tail++] = Node{1, n, 0};
for (int i = 1; i <= n; i++) {
int cur = -1;
int L = 0, R = tail-1;
while (L <= R) {
int mid = (L+R)>>1;
if (que[mid].l <= i) {
cur = mid;
L = mid + 1;
}
else
R = mid - 1;
}
int p = que[cur].p;
dp[i] = dp[p] + w(p, i);
cur = -1;
while (tail && dp[i] + w(i, que[tail-1].l) <= dp[que[tail-1].p] + w(que[tail-1].p, que[tail-1].l))
cur = que[--tail].l;
L = que[tail-1].l, R = que[tail-1].r;
while (L <= R) {
int mid = (L+R) >> 1;
if (dp[i] + w(i, mid) <= dp[que[tail-1].p] + w(que[tail-1].p, mid)) {
que[tail-1].r = mid - 1;
R = mid - 1;
cur = mid;
}
else
L = mid + 1;
}
if (cur != -1)
que[tail++] = Node{cur, n, i};
}