决策单调性优化dp
决策单调性优化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\)，从栈顶向下依次考虑：
- 若新决策在 \(j\) 优于老决策，则退栈并抛弃老决策
- 否则，转折点一定在当前这个老决策的区间中，二分这个位置
- 新决策入栈
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};
}