区间DP四边形不等式优化
石子合并
先看一道最经典的区间DP题洛谷P1880 石子合并
题意
有一个圆形的操场，放着N堆石子，我们只能将相邻的两堆石子合并成一堆，花费是两堆石子数的和，问将N堆合并成一堆的最大最小花费是多少。
思路
以最大值为例，我们定义$dp_{i, j}$表示将第$i$和第$j$堆石子合并的最大花费，我们从小区间开始枚举，通过状态转移方程求的大区间的最优解。对于求$dp_{i, j}$时，我们枚举$k \quad (i \le k < j)$，找到最大的$dp_{i, k} + dp_{k + 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(n^3)$的，对于大数据肯定是会很慢的，如果满足某些条件，可以将类似的DP优化成$O(n^2)$，大大降低复杂度。
对于上面的状态转移方程可以写成这样的形式 $$ dp(l, r) = min_{l \le k \le r - 1} \lbrace dp(l, k) + dp(k + 1, r) \rbrace + w(l, r) \quad (1 \le l \le r \le n) $$
区间包含单调性
对于任意的$l \le l’ \le r’ \le r$，均有$w(l’, r’) \le w(l, r)$成立，则称函数$w$对于区间包含关系具有单调性。
四边形不等式
如果对于任意的$l_1 \le l_2 \le r_1 \le r_2$，均有$w(l_1, r_1) + w(l_2, r_2) \le w(l_1, r_2) + w(l_2, r_1)$成立，则称函数$w$满足四边形不等式，也叫做交叉小于包含。
引理1
若关于区间包含的单调性函数$w(l, r)$满足四边形不等式，则状态$dp(l, r)$也满足四边形不等式。
定义$s_{k, l, r} = dp_{l, k} + dp_{k + 1, r} + w(l, r)$表示当决策为$k$时的状态值，任取$l_1 \le l_2 \le r_1 \le r_2$，记$u = \mathop{Best}\limits_{l_1 \le k < r_2}s_{k, l_1, r_2}$，$v = \mathop{Best}\limits_{l_2 \le k < r_1}s_{k, l_2, r_1}$分别表示状态$dp_{l_1, r_2}$和$dp_{l_2, r_1}$的最优抉择点。
若$u \le v$，则$l_1 \le u < r_1, l_2 \le v < r_2$，因此 $$ dp_{l_1, r_1} \le s_{u, l_1, r_1} = dp_{l_1. u} + dp_{u + 1, r_1} + w(l_1, r_1) \quad (1) \\ dp_{l_2, r_2} \le s_{v, l_2, r_2} = dp_{l_2, v} + dp_{v + 1, r_2} + w(l_2, r_2) \quad (2) $$ 再由$u + 1 \le v + 1 \le r_1 \le r_2$和归纳假设知 $$ dp_{u + 1, r_1} + dp_{v + 1, r_2} \le dp_{u + 1, r_2} + dp_{v + 1, r_1} \quad (3) $$ 将$(1)$和$(2)$相加，得 $$ dp_{l_1, r_1} + dp_{l_2, r_2} \le dp_{l_1, u} + dp_{l_2, v} + dp_{u + 1, r_1} + dp_{v + 1, r_2} + w(l_1, r_1) + w(l_2, r_2) \quad (4) $$ 将$(3)$代入$(4)$中，并且根据$w$函数满足四边形不等式，得 $$ \begin{aligned} dp_{l_1, r_1} + dp_{l_2, r_2} \le& dp_{l_1, u} + dp_{l_2, v} + dp_{u + 1, r_2} + dp_{v + 1, r_1} + w(l_1, r_2) + w(l_2, r_1) \\ \le& s_{u, l_1, r_2} + s_{v, l_2, r_1} = dp_{l_1, r_2} + dp_{l_2, r_1} \end{aligned} $$
若$u > v$，则$l_1 \le v \le r_1$，$l_2 \le u \le r_2$，因此 $$ dp_{l_1, r_1} \le s_{v, l_1, r_1} = dp_{l_1, v} + dp_{v + 1, r_1} + w(l_1, r_1) \quad (5) \\ dp_{l_2, r_2} \le s_{u, l_2, r_2} = dp_{l_2, u} + dp_{u + 1, r_2} + w(l_2, r_2) \quad (6) $$ 再由$l_1 \le l_2 \le v \le u$和归纳假设知 $$ dp_{l_1, v} + dp_{l_2, u} \le dp_{l_1, u} + dp_{l_2, v} \quad (7) $$ 将$(5)$和$(6)$相加，得 $$ dp_{l_1, r_1} + dp_{l_2, r_2} \le dp_{l_1, v} + dp_{l_2, u} + dp_{v + 1, r_1} + dp_{u + 1, r_2} + w(l_1, r_1) + w(l_2, r_2) \quad (8) $$ 将$(7)$代入$(8)$中，并且根据$w$函数满足四边形不等式，得 $$ \begin{aligned} dp_{l_1, r_1} + dp_{l_2, r_2} \le& dp_{l_1, u} + dp_{l_2, v} + dp_{v + 1, r_1} + dp_{u + 1, r_2} + w(l_1, r_2) + w(l_2, r_1) \\ \le& s_{u, l_1, r_2} + s_{v, l_2, r_1} = dp_{l_1, r_2} + dp_{l_2, r_1} \end{aligned} $$
综上所述，两种情况都有$dp_{l_1, r_1} + dp_{l_2, r_2} \le dp_{l_1, r_2} + dp_{l_2, r_1}$，则四边形不等式成立
决策单调性
定理1 ：若状态$dp$满足四边形不等式，定义$m_{l, r} = \min\lbrace k : dp_{l, r} = s_{k, l, r} \rbrace$表示最优决策点，则有 $$ m_{l, r - 1} \le m_{l, r} \le m_{l + 1, r} $$ 记$u = m_{l, r}$，$k_1 = m{l, r - 1}$ ，$k_2 = m_{l + 1, r}$
若$k_1 > u$，则$u + 1 \le k_1 + 1 \le r - 1 \le r$，因此根据四边形不等式有 $$ dp_{u + 1, r - 1} + dp_{k_1 + 1, r} \le dp_{u + 1, r} + dp_{k_1 + 1, r - 1} \quad (9) $$ 根据$u$是状态$dp_{l, r}$的最优决策点可知 $$ dp_{l, u} + dp_{u + 1, r} \le dp_{l, k_1} + dp_{k_1 + 1, r} \quad (10) $$ 将$(9)$和$(10)$两个不等式相加，得 $$ \begin{aligned} dp_{l, u} + dp_{u + 1, r - 1} \le& dp_{l, k_1} + dp_{k_1 + 1, r - 1} \\ s_{u, l, r - 1} \le& s_{k_1, l, r - 1} \end{aligned} $$ 这与$k_1$是最小的最优决策点矛盾，所以$k_1 \le u$
若$u > k_2$，则$l \le l + 1 \le + k_2 \le u$，根据四边形不等式得 $$ dp_{l, k_2} + dp_{l + 1, u} \le dp_{l, u} + dp_{l + 1, k_2} \quad (11) $$ 根据$k_2$是状态$dp_{l + 1, r}$的最优决策点可知 $$ dp_{l + 1, k_2} + dp_{k_2 + 1, r} \le dp_{l + 1, u} + dp_{u + 1, r} \quad (12) $$ 将$(11)$和$(12)$相加，得 $$ \begin{aligned} dp_{l, k_2} + dp_{k_2 + 1, r} \le& dp_{l, u} + dp_{u + 1, r} \\ s_{k_2, l, r} \le& s_{u, l, r} \end{aligned} $$ 这与$u$是最小的最优决策点矛盾，因此$u \le k_2$
所以，如果我们在计算状态$dp_{l, r}$的同时将最小的最优决策点$m_{l, r}$记录下来，那么我们队决策点$k$的总枚举次数将为 $$ \sum\limits_{1 \le l < r \le n} m_{l + 1, r} - m_{l, r - 1} = \sum\limits_{i = 1}^{n} m_{i, n} - m_{1, i} \le n^{2} $$
四边形不等式优化后的石子合并
因为求最大值时，不满足四边形不等式，只能优化求最小值，并且我们在求解$dp_{l, r}$时，是需要知道$m_{l, r - 1}$和$m_{l + 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;
}