决策单调性优化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]$ 。