本文共 2394 字，大约阅读时间需要 7 分钟。

决策单调性

判断决策单调性可以选择打表，有个比较好用的判断是这样的。

$dp$ 转移式： f ( i ) = min ⁡ j < i { f ( j ) + c a l c ( j , i ) } f(i)=\min_{j<i}\{ f(j)+calc(j,i)\} f(i)=minj<i​{ f(j)+calc(j,i)}

如果任意 $a<b$ 满足 $calc(a,b+1)+calc(a+1,b)\le calc(a,b)+calc(a+1,b+1)$ ，则 $f(i)$ 具有决策单调性。

决策单调性优化 $dp$

• 分治做法

  处理 $solve(l,r,q_l,q_r)$ ，意思是 $q_l$ ~ $q_r$ 的决策点在 $l$ ~ $r$ 之中，现在要分治求 $q_l$ ~ $q_r$ 的决策点。

  $mid=\frac{q_l+q_2}{2}$ ，遍历 $l$ ~ $r$ 求出 $mid$ 的决策点 $p$ 。

  递归处理 $solve(l,p,q_l,mid-1)$ ， $solve(l,p,mid+1,q_r)$ 。

  缺点：有些情况只是遍历 $l$ ~ $r$ 难求出 $mid$ 的决策点，这时候要 $cdq$ 分治里面套决这个分治 ，见例题。

• 单调栈做法

  （我今天之前只会这种做法2333

  用单调栈维护若干个单元三元组 $(p,l,r)$ 表示 $l$ ~ $r$ 的决策点为 $p$ 。

  刚开始单调栈为空。

  每求出一个 $f(x)$ ，就更新单调栈中的三元组，具体：从栈中取出一个三原组 $(p,l,r)$ 然后 $check$ $f(l)$ 从 $x$ 转移过来更优还是 $p$ 转移过来更优。如果 $x$ 更优，就把这个三元组删除。否则就在 $l$ ~ $r$ 中二分出一个点 $l^{\prime }$ 满足从 $x$ 转移过来更优。最后把 $(x,l^{\prime },n)$ 加入单调栈。

  $PS$ ：为什么可以这么做就不赘述了，其实挺显然的。

gym 102904B Dispatch Money

分治套分治做法+逆序对

#include <bits/stdc++.h>#define N 300005using namespace std;typedef long long ll;const ll inf=1e17;int n,co,a[N],x=1,y,t[N]; ll ans[N],cnt;int sum(int pos){    int res=0; for(;pos;pos-=pos&-pos) res+=t[pos]; return res; }void add(int pos,int c){    for(;pos<=n;pos+=pos&-pos) t[pos]+=c; }ll ask(int l,int r){   	while(x>l) cnt+=sum(a[x-1]), add(a[x-1],1), --x; 	while(y<r) cnt+=y-x+1-sum(a[y+1]), add(a[y+1],1), ++y; 	while(x<l) add(a[x],-1), cnt-=sum(a[x]), ++x; 	while(y>r) add(a[y],-1), cnt-=y-x-sum(a[y]), --y; 	return cnt; }void solve(int l,int r,int ql,int qr){   	if(ql>qr)return;	int mid=(ql+qr)>>1,v=0; ll now,m=inf;	for(int i=l;i<=r&&i<mid;i++)		if((now=(ans[i]+ask(i+1,mid)))<m) m=now,v=i; ans[mid]=min(m+co,ans[mid]);	solve(l,v,ql,mid-1),solve(v,r,mid+1,qr);}void cdq(int l,int r){   	if(l==r)return;	int mid=(l+r)>>1;	cdq(l,mid);	solve(l,mid,mid+1,r);	cdq(mid+1,r);}int main(){   	cin>>n>>co;	for(int i=1;i<=n;i++)		scanf("%d",&a[i]),ans[i]=inf;	cdq(0,n);	cout<<ans[n]<<endl;}