专栏文章

四边形不等式和决策单调性

___H_J_M__
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miouzxry
此快照首次捕获于
2025/12/03 01:35
3 个月前
此快照最后确认于
2025/12/03 01:35
3 个月前
查看原文

四边形不等式的定义

当对于a,b,c,da,b,c,d满足a≤b≤c≤da\le b\le c\le d时，
w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d)+w(b,c)\ge w(a,c)+w(b,d)
称ww满足四边形不等式。

第一类DP优化

fi=min⁡j<i{fj+w(j+i)}f_i=\min_{j<i}\{f_j+w(j+i)\}

决策单调性

指的是fif_i的决策点jj满足单调性，
相当于jj 随着 ii 的增大而增
当新加入的ii是新的决策点时，相当于:
fi′+wi,i′<fi′+wj,i′f_{i'}+w_{i,i'}<f_{i'}+w_{j,i'}
因而后面的连续一段的决策点都为ii
因此新加入元素(pos,n,i)(pos,n,i),原尾部元素rr变为pos−1pos-1

算法实现

单调队列 维护决策集合P
单调队列中储存了一个三元组(l,r,j),表示,从l到r的最优决策点都为jj
对于每一个i∈[1,n]i\in [1,n]，执行下面操作：
  1. 删除无效队头：当队头为(l,r,j)，若r≤i−1r\le i-1，说明当前对头对于答案无效，弹出对头。否则将l设为i
  2. 取出队头的最优决策点，更新当前fif_i
  3. 插入新元素:ii
    (1) 取出当前队尾(l,r,j)(l,r,j)
    (2) 若f[l]+w(i,l)≤f[j]+w(j,l)f[l]+w(i,l)\le f[j]+w(j,l)，则删除队尾，回到(1)操作。
    (3) 用二分在[l,r][l,r]中找出pospos,使pospos前此决策优，pospos后(包含pospos) ii更优，将(l,r,j)(l,r,j)修改为(l,pos−1,j)(l,pos-1,j)
    (4) 将 (pos,n,i)(pos,n,i) 放入队尾
时间复杂度O(n log n)O(n\ log\ n)。
代码实现
CPP
int n;
int l,r,q[N];
int L[N],R[N];
int w(int x,int y);
void solve(){//写法一，加入f[0]
	l=1,r=1,q[1]=0;
	L[0]=1,R[0]=n;
	for(int i=1;i<=n;i++){
		while(l<=r && R[q[l]]<i) //弹出队首无用项
			l++;
		f[i]=w(q[l],i);
		while(l<=r && w(i,L[q[r]])<=w(q[r],L[q[r]]))//弹出队尾无用项 
			r--;
		int ll=L[q[r]],rr=n+1;
		while(ll<rr){//二分获得pos
			int mid=ll+rr>>1;
			if(w(i,mid)<=w(q[r],mid)) rr=mid;
			else ll=mid+1;
		}
		if(ll>n) continue;
		R[q[r]]=ll-1;
		q[++r]=i;
		L[i]=ll,R[i]=n;
	}
}

void solve(){//写法二，不加入f[0]
	l=1,r=0;
	for(int i=1;i<=n;i++){
		int ans=n+1;
		L[q[r]]=max(L[q[r]],i);
		while(l<=r && w(i,L[q[r]])>=w(q[r],L[q[r]]))//弹出队尾无用项 
			r--;
		if(l<=r && w(i,R[q[r]])>=w(q[r],R[q[r]])){
			ans=R[q[r]]+1;
			int ll=L[q[r]],rr=R[q[r]];
			while(ll<=rr){//二分获得pos
				int mid=ll+rr>>1;
				if(w(i,mid)>=w(q[r],mid)) ans=mid,rr=mid-1;
				else ll=mid+1;
			}
			R[q[r]]=ans-1;
		}
		if(l>r) q[++r]=i,L[i]=i,R[i]=n;
		if(ans!=n+1) q[++r]=i,L[i]=ans,R[i]=n;
		while(l<=r && R[q[l]]<i) //弹出队首无用项
			l++;
		L[q[l]]=i;
		f[i]=max(f[i],w(q[l],i));
	}
}
分治
假设已知[l,r][l,r]的最优决策在[L,R][L,R]上。
定义mid=l+r>>1mid=l+r>>1,设dp[mid]dp[mid]的最优决策为pp,根据决策单调性,可知[l,mid−1][l,mid−1]的最优决策在[L,p][L,p]内,[mid+1,r][mid+1,r]的最优决策在[p,R][p,R]内。
于是将问题分割成了同类型的规模更小的问题，便可递归分治。
时间复杂度O(n logn)O(n\ logn)
代码实现
CPP
int w(int j,int i);
void DP(int l,int r,int ll,int rr) {
	int mid=l+r>>1,k=ll;
	for (int j=ll;j<=min(rr,mid-1);j++)//寻找当前决策点
		if (w(j,mid)<w(k,mid)) k=j;
	f[mid]=w(k,mid);
	if(l<mid) DP(l,mid-1,ll,k);
	if(r>mid) DP(mid+1,r,k,rr);
}

第二类DP优化

fi,j=min⁡i≤k≤j{fi,k+fk+1,j}+wi,jf_{i,j}=\min_{i\le k \le j}\{f_{i,k}+f_{k+1,j}\}+w_{i,j}

决策单调性

当 i<i′≤j<j′i<i'\le j < j',满足：
Pi，j′≤Pi′,jP_{i，j'}\le P_{i',j} 且 Pi,j−1≤Pi,j≤Pi+1,jP_{i,j-1}\le P_{i,j}\le P_{i+1,j}

代码实现

CPP
int w(int j,int i);
for(int i=1;i<=n;i++) f[i][i]=f[i+1][i]=f[i][i-1]=0,p[i][i]=i;
for(int len=2;len<=n;len++){
	for(int i=1;i+len-1<=n;i++){
		int j=i+len-1;
		for(int k=p[i][j-1];k<=p[i+1][j];k++){
			if(f[i][j]>f[i][k-1]+f[k+1][j]+w(i,j)){
				f[i][j]=f[i][k-1]+f[k+1][j]+w(i,j);
				p[i][j]=k;
			}
		}
	}
}
cout<<f[1][n]<<'\n';

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...