决策单调性优化dp

用来存下板子。。。证明或详细讲解请参考其他blog

决策单调性

可离线

分治

例：CF321E

void solve(int s,int l=1,int r=n,int nl=0,int nr=n-1)
{
    if(l>r) return;
    int m = mid,from; f[s][m]=inf; 
    fp(i,nl,min(nr,m-1))
        if(f[s-1][i]+cost(i+1,m)<f[s][m])
            f[s][m]=f[s-1][i]+cost(i+1,m),from=i;
    solve(s,l,m-1,nl,from),solve(s,m+1,r,from,nr);
}

不可离线

写法参考自：浅析1D1D动态规划的优化

确定 $f[3]$ 之前所有状态的最优决策表：

1111111111111222222222222

加入 $f[3]$ 后决策表只能有三种类型

1111111111111222222222222 不变

1111111111111222223333333 占据 $2$ 的一部分

1111113333333333333333333 完全覆盖 $2$

考虑使用栈来维护每个 $i$ 作为决策点的起始位置

设老决策的起点为 $j$，从栈顶向下依次考虑：

1. 若新决策在 $j$ 优于老决策，则退栈并抛弃老决策

2. 否则，转折点一定在当前这个老决策的区间中，二分这个位置

3. 新决策入栈

例： [NOI2009]诗人小G

pr s[MAXN]; int h=0;
LL calc(int i,int j){return f[j]+cost(i,j);}
fp(i,1,n)
{
    pr t=*(ub(s+1,s+h+1,mp(i,inf))-1);

    f[i]=calc(i,t.se),from[i]=t.se;
    
    if(i==n||calc(n,s[h].se)<calc(n,i))continue;

    while(h&&s[h].fi>i&&calc(s[h].fi,s[h].se)>calc(s[h].fi,i))h--;
    int l=max(i+1,s[h].fi),r=n,ans=n;
    while(l<=r)
    {
        if(calc(mid,s[h].se)>calc(mid,i))ans=mid,r=mid-1;
        else l=mid+1;
    }
    s[++h]={ans,i};
}