引用 / 参考:绍兴一中相关课件,Acfboy 的博客。
决策单调性
决策单调性指的是 dp 的决策时的最优位置是单调的。
常见地,若存在:
难点在于观察 (猜) 出其为决策单调,经常可以不证明。一般通过打表观察。
通用的决策单调性分治:
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)
例题
省略推导过程,有:
#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 博文写得太好了!