决策单调性优化DP

发表于

四边形不等式

定义

设 $w(x,y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a,b,c,d$ ，其中 $a\leq b\leq c\leq d$ ，都有 $w(a,d)+w(b,c)\geq w(a,c)+w(b,d)$ 成立，则称函数 $w$ 满足四边形不等式。

定理（另一种定义）

设 $w(x,y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a,b$ ，其中 $a<b$ ，都有 $w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)$ 成立，则函数 $w$ 满足四边形不等式。

证明：

对于 $a<c$ ，有 $w(a,c+1)+w(a+1,c)\geq w(a,c)+w(a+1,c+1)$ 。

对于 $a+1<c$ ，有 $w(a+1,c+1)+w(a+2,c)\geq w(a+1,c)+w(a+2,c+1)$ 。

两式相加，得到 $w(a,c+1)+w(a+2,c)\geq w(a,c)+w(a+2,c+1)$ 。

依此类推，对任意 $a\leq b\leq c$ ，有 $w(a,c+1)+w(b,c)\geq w(a,c)+w(b,c+1)$ 。

同理，对任意的 $a\leq b\leq c\leq d$ ，有 $w(a,d)+w(b,c)\geq w(a,c)+w(b,d)$ 。

一维线性 $DP$ 的四边形不等式优化

对于形如 $F[i]=\min_{0\leq j<i}\{F[j]+val(j,i)\}$ 的状态转移方程，记 $p[i]$ 为令 $F[i]$ 取到最小值的 $j$ 的值，即 $p[i]$ 是 $F[i]$ 的最优决策。若 $p$ 在 $[1,N]$ 上单调不减，则称 $F$ 具有决策单调性。

定理（决策单调性）

在状态转移方程 $F[i]=\min_{0\leq j<i}\{F[j]+val(j,i)\}$ 中，若函数 $val$ 满足四边形不等式，则 $F$ 具有决策单调性。

证明：

$\forall i\in[1,N],\forall j\in[0,p[i]-1]$ ，根据 $p[i]$ 的最优性，有：

$\forall i’\in[i+1,N]$ ，因为 $val$ 满足四边形不等式，有：

移项得：

与第一个等式相加，有：

这个不等式的含义为，以 $p[i]$ 作为 $F[i’]$ 的决策，比以 $j<p[i]$ 作为 $F[i’]$ 的决策更优。换言之， $p[i’]\geq p[i]$ 。所以 $F$ 有决策单调性。

证毕。

当 $F$ 有决策单调性时，我们可以把 $F[i]=\min_{0\leq j<i}\{F[j]+val(j,i)\}$ 的计算时间从 $O(N^2)$ 优化到 $O(N\log N)$ 。

考虑维护 $p$ 数组。最初 $p$ 数组全为 $0$ 。在 $i$ 循环的任意时刻，根据 $p[i]$ 的单调性， $p$ 的情况如下表所示：

当求出一个新的 $F[i]$ 时，我们考虑 $i$ 可以作为哪些 $F[i’]\ (i’>i)$ 的最优决策点。根据决策单调性，最终我们会找到一个位置，在该位置之前， $p$ 数组目前储存的决策都比 $i$ 好，在该位置之后， $p$ 数组目前储存的决策都比 $i$ 差。我们要做的就是快速找到这个位置，在 $p$ 数组中把该位置后的部分均改为 $i$ ：

当然，直接修改效率很低。事实上，我们可以建立一个队列，代替 $p$ 数组。队列中保存若干个三元组 $(j,l,r)$ ，分别表示决策和管辖范围。

另外，队列中没有必要保存管辖 $1\sim i-1$ 的部分，这样我们每次取出对头最为最优决策即可。

例题

P1912 [NOI2009]诗人小G

Solution

我们设 $dp_i$ 表示考虑了前 $i$ 个句子，诗的不协调程度，我们有：

这里面存在大量 $i,j$ 的高次乘积，不适用于单调队列或斜率优化。所以我们尝试判断决策单调性。

我们需要证明：

设 $u=(sum_i+i)-(sum_j+j)-(L-1)$ 。

设 $v=(sum_i+i)-(sum_{j+1}+j+1)-(L-1)$ 。

只需要证明 $|v|^p-|v+(a_{i+1}+1)|^p\geq |u|^p-|u+(a_{i+1}+1)|^p$ 。

显然 $u>v$ ，故只需证明对任意常数 $c$ ，函数 $y=|x|^p+|x+c|^p$ 单调递减即可。

进行分类讨论。

当 $p$ 为奇数，且 $x\in[-c,0]$ 时，函数写作 $y=-x^p-(x+c)^p$ 。对 $x$ 求导，得到 $y’=-p\cdot x^{p-1}-p\cdot (x+c)^{p-1}$ 。

因为 $p>0$ 且 $p$ 为奇数，所以 $y’\leq 0$ ，从而 $y$ 关于 $x$ 单调递减。

类似的，我们可以推出其他情况下同样满足。

综上， $val$ 满足四边形不等式。因此， $F$ 具有决策单调性。

这样，既可将时间复杂度优化至 $O(N\log N)$ 。

Code

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
const int N = 1e5+5;
int T,n,L,p,val[N],pre[N],l,r;
char s[N][40];
long double dp[N];
inl long double Calc(int i,int j){
	int x=val[i]-val[j]+i-j-1-L;
	long double res=1;
	x=x<0?-x:x;
	for(ri i=1;i<=p;++i) res*=x;
	return res+dp[j];
}
il Print(int n){
	if(!n) return ;
	Print(pre[n]);
	for(ri i=pre[n]+1;i<n;++i) printf("%s ",s[i]+1);
	printf("%s\n",s[n]+1);
}
struct Node{
	int j,l,r;
}q[N];
it Get(int i){
	int L=l,R=r;
	while(L<=R){
		int mid=(L+R)>>1;
		if(q[mid].l<=i&&q[mid].r>=i) return q[mid].j;
		if(q[mid].l>i) R=mid-1;
		else L=mid+1;
	}
}
il pop(int i){
	while(l<=r){
		if(q[l].r<=i) ++l;
		else{q[l].l=i+1;break;}
	}
}
il push(int i){
	int k=-1;
	while(l<=r){
		if(Calc(q[r].l,i)<=Calc(q[r].l,q[r].j)) k=q[r--].l;
		else{
			if(Calc(q[r].r,q[r].j)<=Calc(q[r].r,i)) break;
			int L=q[r].l,R=q[r].r;
			while(L<R){
				int mid=(L+R)>>1;
				if(Calc(mid,i)<=Calc(mid,q[r].j)) R=mid;
				else L=mid+1;
			}
			q[r].r=L-1,k=L;
			break;
		}
	}
	if(k==-1) return ;
	q[++r]=(Node){i,k,n};
}
il Solve(){
	read(n),read(L),read(p);
	for(ri i=1;i<=n;++i)
		scanf("%s",s[i]+1),val[i]=strlen(s[i]+1);
	for(ri i=2;i<=n;++i)
		val[i]+=val[i-1];
	l=1,r=1,q[1]=(Node){0,1,n};
	for(ri i=1;i<=n;++i){
		int j=Get(i);
		dp[i]=Calc(i,pre[i]=j);
		pop(i),push(i);
	}
	if(dp[n]>1e18) puts("Too hard to arrange");
	else{
		printf("%.0Lf\n",dp[n]);
		Print(n);
	}
	for(ri i=1;i<=20;++i) putchar('-');
	puts("");
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(T);
	for(ri i=1;i<=T;++i)
		Solve();
	return 0;
}

CF868F Yet Another Minimization Problem

Solution

我们设 $dp_{i,j}$ 表示当前被分成了 $i$ 段，其中第 $i$ 段的末尾为 $j$ 是的最小花费。

容易得出转移方程为：

可以发现 $val$ 满足四边形不等式。

证明如下：

我们需要证明 $val(j,i+1)+val(j+1,i)\geq val(j,i)+val(j+1,i+1)$ 。

我们设 $cnt1,cnt2$ 表示区间 $[j+1,i]$ 中与分别 $a_j,a_{i+1}$ 相等的数的个数。

那么我们有：

$val(j,i+1)+val(j+1,i)=2\cdot val(j+1,i)+cnt1+cnt2+[a_j=a_{i+1}]$ 。

$val(j,i)+val(j+1,i+1)=2\cdot val(j+1,i)+cnt1+cnt2$ 。

两式相减，得到 $[a_j=a_{i+1}]\geq 0$ ，得证。

所以 $dp$ 是满足决策单调性的。

但是我们不能直接像上面那样做，因为我们无法快速计算出 $val(j,i)$ 。

事实上，我们可以像莫队那样直接跳，经过分析，复杂度是正确的。

code

二维区间 $DP$ 的四边形不等式优化

对于形如 $dp_{i,j}=\min_{i\leq k<j}\{dp_{i,k}+dp_{k+1,j}+w(i,j)\}$ 的状态转移方程，我们也可以利用四边形不等式进行优化。

定理

在状态转移方程 $F[i,j]=\min_{i\leq k<j}\{F[i,k]+F[k+1,j]+w(i,j)\}$ 中（特别的， $F[i,i]=w(i,i)=0$ ），如果下面两个条件成立：

  1. $w$ 满足四边形不等式。
  2. 对任意的 $a\leq b\leq c\leq d$ ，有 $w(a,d)\geq w(b,c)$ 。

那么 $F$ 也满足四边形不等式。

证明

当 $i+1=j$ 时， $F[i,j+1]+F[i+1,j]=F[i,i+2]+F[i+1,i+1]=F[i,i+2]$ 。

若 $F[i,i+2]$ 的最优决策是 $i+1$ ，则：

类似的，可以得到最优决策是 $i$ 时， $F[i,i+2]\geq F[i,j]+F[i+1,j+1]$ 。

所以当 $j-i=1$ 时，四边形不等式对 $F[i,j]$ 成立。

接下来，我们使用数学归纳法证明。

假设当 $j-i<k$ 时，四边形不等式对 $F(i,j)$ 成立。考虑 $j-i=k$ 的情况，设 $F[i,j+1]$ 以 $x$ 为最优决策， $F[i+1,j]$ 以 $y$ 为最优决策。

不妨设 $i+1\leq x\leq y$ 。

根据 $x,y$ 的最优性，有：

对于 $F[i,j],F[i+1,j+1]$ ， $x,y$ 不一定是最优决策，故：

因为 $w$ 满足四边形不等式，所以 $w(i,j+1)+w(i+1,j)\geq w(i,j)+w(i+1,j+1)$ 。

根据归纳假设，有 $F[x+1,j+1]+F[y+1,j]\geq F[x+1,j]+F[y+1,j+1]$ 。

由这 $4$ 个式子，我们可以得到 $F[i,j+1]+F[i+1,j]\geq F[i,j]+F[i+1,j+1]$ 。

证毕。

定理（二维决策单调性）

在状态转移方程 $F[i,j]=\min_{i\leq k<j}\{F[i,k]+F[k+1,j]+w(i,j)\}$ 中（特别的， $F[i,i]=w(i,i)=0$ ），记 $p[i,j]$ 为令 $F[i,j]$ 取到最小的 $k$ 值。

如果 $F$ 满足四边形不等式，那么对于任意 $i<j$ ，有 $p[i,j-1]\leq p[i,j]\leq p[i+1,j]$ 。