算法

四边形不等式优化学习笔记

学会，但没完全学会

参考 肖然的博客

四边形不等式

原形式

有一个双变量函数 $f(x,y)$，如果对于 $\forall a\le b\le c\le d$，都满足 $f(a,d)+f(b,c)\ge f(a,c)+f(b,d)$ 则称其满足 四边形不等式。

等价形式

对于 $\forall a

这一形式的必要性显然，下证其充分性：

若 $a+1 $$ \begin{aligned} f(a,b+1)+f(a+1,b)&\ge f(a,b)+f(a+1,b+1)\cr f(a+1,b+1)+f(a+2,b)&\ge f(a+1,b)+f(a+2,b+1) \end{aligned} $$

两式相加，得

$$f(a,b+1)+f(a+2,b)\ge f(a,b)+f(a+2,b+1)$$

原来的 a+1 可以扩展到 a+2，用类似方法，可扩展成：

$$\forall a^{\prime}>a,f(a,b+1)+f(a^{\prime},b)\ge f(a,b)+f(a^{\prime},b+1)$$

b 的扩展方式类似，就是把原式带入 $b^{\prime}=b-1$ 然后相加即可。

1D1D

$$dp(i)=\min_{j其中 w 函数满足四边形不等式时，转移具有 决策单调性，每次的决策点都在上次的后头，下证之：

单调性证明

设第 i 项的决策点为 $p(i)$，则对 $\forall j $$ \begin{aligned} dp(p(i))+w(p(i),i)&\le dp(j)+w(j,i)\cr w(p(i),i+1)+w(j,i)&\le w(p(i),i)+w(j,i+1) \end{aligned} $$

两式相加，得：

$$dp(p(i))+w(p(i),i+1)\le dp(j)+w(j,i+1)$$

所以 $p(i+1)\ge p(i)$。

P3515 [POI2011]Lightning Conductor

老师的代码交到黑暗爆炸 OJ 被卡了

把原式移项，得 $p=\max(a_j-a_i+\sqrt{\|i-j\|)}$，发现满足决策单调性，只需正着搞一遍，反着搞一遍即可。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int MXN=5e5+5;
int n,arr[MXN];
double p1[MXN],p2[MXN];
template<class T1,class T2>
struct pr{
	T1 fi;T2 se;
	inline pr(T1 fi=0,T2 se=0):fi(fi),se(se){}
};
pr<int,int> q[MXN];int ql,qr;
inline double f(int i,int j){return sqrt(i-j)+arr[j]-arr[i];}
inline void solve(double *p){
	ql=1,qr=0;
	for(int i=1;i<=n;i++){
		while(ql<=qr && f(max(q[qr].se,i),i)>=f(max(q[qr].se,i),q[qr].fi))qr--;
		if(ql>qr)q[++qr]=pr<int,int>(i,1);
		else{
			int l=max(i,q[qr].fi),r=n+1;
			while(l<r){
				int mid=(l+r)>>1;
				f(mid,i)>=f(mid,q[qr].fi)?r=mid:l=mid+1;
			}
			q[++qr]=pr<int,int>(i,l);
		}
		while(ql<qr && q[ql+1].se<=i)ql++;
		p[i]=f(i,q[ql].fi);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",arr+i);
	solve(p1);
	reverse(arr+1,arr+1+n);
	solve(p2);
	for(int i=1;i<=n;i++)
		printf("%d\n",(int)ceil(max(p1[i],p2[n-i+1])));
	return 0;
}

P1912 [NOI2009] 诗人小G

依然有决策单调性，推导甚是麻烦，略。这个答案超过 1e18 不太好搞，不妨用 long double 存答案，最后再判。

代码：（加了快读就是最优解）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2>struct pr{T1 x;T2 y;};
template<class T1,class T2>inline pr<T1,T2> mp(T1 x,T2 y){return pr<T1,T2>{x,y};}

typedef long long ll;
typedef long double ld;
const int MXN=1e5+5;
const int MXS=35;
int t,n,stdlen,p,len[MXN];
char str[MXN][MXS];

inline ld qpow(ld x,int y){
	ld r=1;
	while(y){
		if(y&1)r*=x;
		x*=x,y>>=1;
	}
	return r;
}
#define w(x,y) (dp[x]+qpow(abs(len[y]-len[x]-stdlen),p))



int ql,qr,tran[MXN];
pr<int,int> q[MXN];
ld dp[MXN];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&stdlen,&p);stdlen++;
		q[qr=ql=1]=mp(0,1);
		for(int i=1;i<=n;i++){
			str[i][0]=0;
			scanf("%s",str[i]+1);
			len[i]=strlen(str[i]+1)+len[i-1]+1;
		}
		for(int i=1;i<=n;i++){
			while(ql<qr && q[ql+1].y<=i)ql++;
			tran[i]=q[ql].x;
			dp[i]=w(tran[i],i);

			while(ql<=qr && w(i,q[qr].y)<w(q[qr].x,q[qr].y))qr--;
			if(ql>qr)q[++qr]=mp(i,i);
			else{
				int l=q[qr].y,r=n+1,mid;
				while(l<r){
					mid=(l+r)>>1;
					if(w(i,mid)<w(q[qr].x,mid))r=mid;
					else l=mid+1;
				}
				if(l<=n)q[++qr]=mp(i,l);
			}
		}
		if(dp[n]>1e18)printf("Too hard to arrange\n");
		else{
			printf("%lld\n",(ll)dp[n]);
			for(int i=n;i;i=tran[i])str[i][0]=-1;
			for(int i=1;i<=n;i++){
				printf("%s",str[i]+1);
				putchar(str[i][0]?'\n':' ');
			}
		}
		puts("--------------------");
	}
	return 0;
}

2D1D

对于形式如下的 dp 转移：

$$ \begin{aligned} dp(i,j)=&\min_{k\in[i,j)}(dp(i,k)+dp(k+1,j))+w(i,j)\cr dp(i,j)=&\min_{k\in[i,j)}(dp(i-1,k)+w(k+1,j))\cr \end{aligned} $$

且：

  • 函数 w 满足四边形不等式
  • $\forall a\le b\le c\le d, w(a,d) \ge w(b,c)$

可以证明 $p(i,j-1) \le p(i,j) \le p(i+1,j)$，k 只需在这个范围内枚举，复杂度变为 $O(n^2)$，不会证，详见 OI-wiki。 实际运用中打个表就知道满不满足决策单调性了。

AcWing 282. 石子合并

转移：

$$ dp(i,j)=\min_{k\in[i,j)}(dp(i,k)+dp(k+1,j))+\underbrace{s[j]-s[i-1]}_{w(i,j)}; $$

$w(i,j)$ 满足条件，所以有决策单调性。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<bits/stdc++.h>
using namespace std;
const int MXN=305;
int n,arr[MXN],dp[MXN][MXN],t[MXN][MXN];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",arr+i);
		t[i][i]=i;
		arr[i]+=arr[i-1];
	}
	for(int i=n;i;i--)
		for(int j=i+1;j<=n;j++){
		    dp[i][j]=1e9;
			for(int k=t[i][j-1];k<=t[i+1][j];k++)
				if(dp[i][j]>dp[i][k]+dp[k+1][j]){
					dp[i][j]=dp[i][k]+dp[k+1][j];
					t[i][j]=k;
				}
			dp[i][j]+=arr[j]-arr[i-1];
		}
	/*for(int i=1;i<=n;i++,putchar('\n'))
		for(int j=1;j<=n;j++)
			printf("%3d",t[i][j]);*/
	printf("%d",dp[1][n]);
	return 0;
}

AcWing 336. 邮局

山区建小学，每个区间都建在中位数上，依然有决策单调性。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<bits/stdc++.h>
using namespace std;
const int MXP=35;
const int MXN=305;
int n,p,x[MXN],sx[MXN];
int dp[MXP][MXN],t[MXP][MXN];
inline int w(int l,int r){
	int mid=(l+r)>>1;
	return sx[r]+sx[l-1]-(sx[mid]<<1)+x[mid]*((mid<<1)-l-r+1);
}
int main(){
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++){
		scanf("%d",x+i);
		sx[i]=sx[i-1]+x[i];
		if(i<=p)t[i+1][i]=i-1;
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int j=1;j<=n;j++){
		t[p+1][j]=j-1;
		for(int i=min(j,p);i;i--)
			for(int k=t[i][j-1];k<=t[i+1][j];k++){
				if(dp[i][j]>dp[i-1][k]+w(k+1,j)){
					dp[i][j]=dp[i-1][k]+w(k+1,j);
					t[i][j]=k;
				}
			}
	}
	/*
	for(int i=1;i<=p+1;i++,putchar('\n'))
		for(int j=1;j<=n;j++)
			cerr<<t[i][j]<<" ";
			*/

	printf("%d",dp[p][n]);

	return 0;
}