引用/参考：绍兴一中相关课件，Acfboy 的博客。

决策单调性

决策单调性指的是 dp 的决策时的最优位置是单调的。

常见地，若存在： $dp_i = f(dp_j)$ 中，$i$ 的决策位置是 $pos_i$，那么对于所有 $i\ge2,pos_i \ge pos_{i-1}$。

难点在于观察(猜)出其为决策单调，经常可以不证明。一般通过打表观察。

通用的决策单调性分治：

solve(l,r,L,R): l,r 表示区间范围, L,R 表示决策范围
    if(l>r) exit
    mid = (l+r) / 2
    pos = query[L,R,mid] 从 L 到 R 中选取 mid 的最优决策
    f[mid] = g(pos)
    solve(l,mid-1,L,pos)
    solve(mid+1,r,pos,R)

例题

Luogu3648 [APIO2014]序列分割。

省略推导过程，有：$f_{i,k}=\max{f_{j,k-1}+(s_i−s_j)×s_j}$，然后发现决策满足单调性，套上文的通用模板。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s[N],f[N][205],pre[N][205];
inline void solve(int l,int r,int L,int R,int k){
    if(l>r) return;
    int mid=(l+r)>>1;
    int pos=0,maxx=0;
    for(int i=L;i<=R;i++){
        int t=f[i][k-1]+(s[mid]-s[i])*s[i];
        if(t>maxx){
            maxx=t;
            pos=i;
        }
    }
    f[mid][k]=maxx;pre[mid][k]=pos;
    solve(l,mid-1,L,pos,k);solve(mid+1,r,pos,R,k);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    for(int i=1;i<=m;i++) solve(1,n,1,n,i);
    printf("%lld\n",f[n][m]);
    for(int x=n,i=m;i>=1;i--){
        x=pre[x][i];
        printf("%lld ",x);
    }
    return 0;
}

比斜率优化多一只 log，但是能卡过去。