引用/参考:绍兴一中相关课件,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)
例题
省略推导过程,有:$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,但是能卡过去。
受宠若惊
神仙 acfboy 博文写得太好了!