石子合并

先看一道最经典的区间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;
}

参考

OI-Wiki 四边形不等式优化

B站 bewildRan - 0225【四边形不等式优化DP】