区间DP四边形不等式优化
石子合并
先看一道最经典的区间DP题洛谷P1880 石子合并
题意
有一个圆形的操场，放着N堆石子，我们只能将相邻的两堆石子合并成一堆，花费是两堆石子数的和，问将N堆合并成一堆的最大最小花费是多少。
思路
以最大值为例，我们定义dpi,j表示将第i和第j堆石子合并的最大花费，我们从小区间开始枚举，通过状态转移方程求的大区间的最优解。对于求dpi,j时，我们枚举k(i≤k<j)，找到最大的dpi,k+dpk+1,j+cost(i,j)即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
const ll mod = 998244353;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e4 + 5;
int a[205], pre[205];
int dp1[205][205], dp2[205][205]; // 最大，最小
int main() {
// freopen("in.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1; i <= (n<<1); i++) {
pre[i] = pre[i - 1] + a[i];
}
// 从小到大枚举长度
for (int len = 2; len <= n; len++) {
for (int i = 1, j = len; j <= (n<<1); i++, j++) {
dp2[i][j] = inf;
// 枚举中间最优点k
for (int k = i; k < j; k++) {
dp1[i][j] = max(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + pre[j] - pre[i - 1]);
dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1]);
}
}
}
int mx = 0, mi = inf;
for (int i = 1, j = n; j <= (n<<1); i++, j++) {
mx = max(mx, dp1[i][j]);
mi = min(mi, dp2[i][j]);
}
cout << mi << '\n' << mx << '\n';
return 0;
}
四边形不等式优化
很显然上面的做法的时间复杂度为O(n3)的，对于大数据肯定是会很慢的，如果满足某些条件，可以将类似的DP优化成O(n2)，大大降低复杂度。
对于上面的状态转移方程可以写成这样的形式
dp(l,r)=minl≤k≤r−1{dp(l,k)+dp(k+1,r)}+w(l,r)(1≤l≤r≤n)
区间包含单调性
对于任意的l≤l’≤r’≤r，均有w(l’,r’)≤w(l,r)成立，则称函数w对于区间包含关系具有单调性。
四边形不等式
如果对于任意的l1≤l2≤r1≤r2，均有w(l1,r1)+w(l2,r2)≤w(l1,r2)+w(l2,r1)成立，则称函数w满足四边形不等式，也叫做交叉小于包含。
引理1
若关于区间包含的单调性函数w(l,r)满足四边形不等式，则状态dp(l,r)也满足四边形不等式。
定义sk,l,r=dpl,k+dpk+1,r+w(l,r)表示当决策为k时的状态值，任取l1≤l2≤r1≤r2，记u=l1≤k<r2Bestsk,l1,r2，v=l2≤k<r1Bestsk,l2,r1分别表示状态dpl1,r2和dpl2,r1的最优抉择点。
若u≤v，则l1≤u<r1,l2≤v<r2，因此
dpl1,r1≤su,l1,r1=dpl1.u+dpu+1,r1+w(l1,r1)(1)dpl2,r2≤sv,l2,r2=dpl2,v+dpv+1,r2+w(l2,r2)(2)
再由u+1≤v+1≤r1≤r2和归纳假设知
dpu+1,r1+dpv+1,r2≤dpu+1,r2+dpv+1,r1(3)
将(1)和(2)相加，得
dpl1,r1+dpl2,r2≤dpl1,u+dpl2,v+dpu+1,r1+dpv+1,r2+w(l1,r1)+w(l2,r2)(4)
将(3)代入(4)中，并且根据w函数满足四边形不等式，得
dpl1,r1+dpl2,r2≤≤dpl1,u+dpl2,v+dpu+1,r2+dpv+1,r1+w(l1,r2)+w(l2,r1)su,l1,r2+sv,l2,r1=dpl1,r2+dpl2,r1
若u>v，则l1≤v≤r1，l2≤u≤r2，因此
dpl1,r1≤sv,l1,r1=dpl1,v+dpv+1,r1+w(l1,r1)(5)dpl2,r2≤su,l2,r2=dpl2,u+dpu+1,r2+w(l2,r2)(6)
再由l1≤l2≤v≤u和归纳假设知
dpl1,v+dpl2,u≤dpl1,u+dpl2,v(7)
将(5)和(6)相加，得
dpl1,r1+dpl2,r2≤dpl1,v+dpl2,u+dpv+1,r1+dpu+1,r2+w(l1,r1)+w(l2,r2)(8)
将(7)代入(8)中，并且根据w函数满足四边形不等式，得
dpl1,r1+dpl2,r2≤≤dpl1,u+dpl2,v+dpv+1,r1+dpu+1,r2+w(l1,r2)+w(l2,r1)su,l1,r2+sv,l2,r1=dpl1,r2+dpl2,r1
综上所述，两种情况都有dpl1,r1+dpl2,r2≤dpl1,r2+dpl2,r1，则四边形不等式成立
决策单调性
定理1 ：若状态dp满足四边形不等式，定义ml,r=min{k:dpl,r=sk,l,r}表示最优决策点，则有
ml,r−1≤ml,r≤ml+1,r
记u=ml,r，k1=ml,r−1 ，k2=ml+1,r
若k1>u，则u+1≤k1+1≤r−1≤r，因此根据四边形不等式有
dpu+1,r−1+dpk1+1,r≤dpu+1,r+dpk1+1,r−1(9)
根据u是状态dpl,r的最优决策点可知
dpl,u+dpu+1,r≤dpl,k1+dpk1+1,r(10)
将(9)和(10)两个不等式相加，得
dpl,u+dpu+1,r−1≤su,l,r−1≤dpl,k1+dpk1+1,r−1sk1,l,r−1
这与k1是最小的最优决策点矛盾，所以k1≤u
若u>k2，则l≤l+1≤+k2≤u，根据四边形不等式得
dpl,k2+dpl+1,u≤dpl,u+dpl+1,k2(11)
根据k2是状态dpl+1,r的最优决策点可知
dpl+1,k2+dpk2+1,r≤dpl+1,u+dpu+1,r(12)
将(11)和(12)相加，得
dpl,k2+dpk2+1,r≤sk2,l,r≤dpl,u+dpu+1,rsu,l,r
这与u是最小的最优决策点矛盾，因此u≤k2
所以，如果我们在计算状态dpl,r的同时将最小的最优决策点ml,r记录下来，那么我们队决策点k的总枚举次数将为
1≤l<r≤n∑ml+1,r−ml,r−1=i=1∑nmi,n−m1,i≤n2
四边形不等式优化后的石子合并
因为求最大值时，不满足四边形不等式，只能优化求最小值，并且我们在求解dpl,r时，是需要知道ml,r−1和ml+1,r的，所以l需要从大到小枚举，r需要从小到大枚举
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
const ll mod = 998244353;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e4 + 5;
int a[205], pre[205];
int dp1[205][205], dp2[205][205], m[205][205];
int main() {
// freopen("in.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1; i <= (n<<1); i++) {
pre[i] = pre[i - 1] + a[i];
m[i][i] = i;
}
for (int i = (n<<1); i >= 1; i--) {
for (int j = i + 1; j <= (n<<1); j++) {
dp2[i][j] = inf;
dp1[i][j] = max(dp1[i + 1][j], dp1[i][j - 1]) + pre[j] - pre[i - 1];
for (int k = m[i][j - 1]; k <= m[i + 1][j]; k++) {
if (dp2[i][j] > dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1]) {
dp2[i][j] = dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1];
m[i][j] = k;
}
}
}
}
int mi = inf, mx = 0;
for (int i = 1, j = n; j <= (n<<1); i++, j++) {
mi = min(mi, dp2[i][j]);
mx = max(mx, dp1[i][j]);
}
cout << mi << '\n' << mx << '\n';
return 0;
}
参考
OI-Wiki 四边形不等式优化
B站 bewildRan - 0225【四边形不等式优化DP】