决策单调性优化DP | Eric Way's Personal Site

考虑状态转移方程： $$ f(i)=\min_{j \le i} \{g(j)+w(i,j)\} $$ 其中最小值可能改为最大值；$j \le i$可能改为$j<i$或$j \not = i$（先考虑$j<i$，再倒序处理）。设 $$ p(i)=\arg \min_{j \le i} \{g(j)+w(i,j)\} $$ 若满足$p(i)$（非严格）单调递增，则可使用决策单调性优化。对于每个$j$，$p(i)=j$的解要么没有，要么在某个连续的区间上。用一个三元组$(j,l,r)$表示 $$ \forall i \in [l,r] \; p(i)=j $$ 维护一个由上述三元组构成的单调队列。当遍历所有$i$时，

更新队首区间范围。若$i$已经超过当前队首所表示的区间，则队首不再有用，故弹出队首。否则，将当前队首的$l$变为$i$。
清除无用队尾。若$i$对队尾区间内的所有值均比当前队尾所取参数更优，则弹出队尾。注意，这里我们把$i$看成是一个$j$，和当前队尾所取的$j’$比较当当前队尾区间开头作为$i’$时，$j$和$j’$谁更优。注意此时有以下三种可能情形：
1. 单调队列被清空了；
2. 单调队列被删除了一些元素，但没被删光；
3. 单调队列未被删除任何元素。
讨论：
1. 对于上述第一种情况，这表明$i$打败了所有的当前方案，我们更新在区间$[i , n]$上的最优解为$i$。
2. 对于第二和第三种情况，我们认为在队尾可能存在$i$作为最优解更新的区间，因此对队尾的区间进行二分搜索，寻找最小的$i’$，使对它而言，$i$作为$j$比当前队尾所取的$j’$更优。但这个$i’$有可能不存在，即对整个队尾的区间而言，队尾的所取的$j$确实已经比$i$更优，因此搜索的初始值设置为队尾的$r+1$。除了发生第三种情况且同时$i’$不存在（即停留在初始值$n+1$），我们不需要更新队列外，我们更新在区间$[i’,n]$上的最优解为$i$。

对于决策单调性的证明，严格做法是四边形不等式，但竞赛中也可通过猜想结合打表来处理。注意：决策单调性的成立命题不等价于对于每个$i$，$g(j) + w(i, j)$具有单调性。这意味着，虽然$p(i) \ge p(i-1)$，但我们不能使用尝试自增$j$的方式为每个$i$进行决策选择。例如，当$p(2)=0$、$p(3)=3$时，可能对于$i=3$而言，$j=1,2$相比于$j=0$并不是更优的决策，因此尝试自增$j$会使得$j$停住不动，无法正确转移到最优解$j=3$。例题：Lightning Conductor

#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(register int i=(int)(from);i>=(int)(to);--i)
#define For(i,to) for(register int i=0;i<(int)(to);++i)
typedef int ll;
typedef long double ld;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}
#define N 512345
int n; int a[N]; 
ld sqr[N], f[N];

struct node {
    int j, l, r;
}q[N]; int head, tail;

ld val(int i, int j) {
    return (ld)a[j] + sqr[i - j] - (ld)a[i];
}

inline bool better(int i, int j1, int j2) {
    return val(i, j1) >= val(i, j2);
}

int binary_search(int i) {
    int l = q[tail].l, r = q[tail].r, j = q[tail].j;
    int ans = r + 1;
    while(l <= r) {
        int mid = l + ((r-l) >> 1);
        if (better(mid, i, j)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

void solve() {
    head=1; tail=0;
    rep(i, 1, n) {
        if (head <= tail && q[head].r == i - 1) ++head;
        else q[head].l = i;

        while(head <= tail && better(q[tail].l, i, q[tail].j)) --tail;
        if (head <= tail) {
            int pos = binary_search(i);
            if (pos <= n) {
                q[tail].r = pos - 1;
                q[++tail] = (node){i, pos, n};
            }
        }
        else {
            q[++tail] = (node){i, i, n};
        } 

        f[i] = max(f[i], val(i, q[head].j));
    }
}

int main() {
    n=read();
    rep(i,1,n){
        sqr[i]=sqrt(i);
        a[i]=read();
    }

    solve();
    reverse(a + 1, a + 1 + n);
    reverse(f + 1, f + 1 + n);
    solve();

    rev(i,n,1) {
        printf("%d\n", (int)ceil(f[i]));
    }
    return 0;
}