区间dp

基本介绍

区间dp，简单来说就是以一个子区间为最小元素，一步步递推到根区间的过程。就是通过一个个小区间的最优解来推出大区间的最优解的过程。

实现过程

（区间dp好难啊啊。。不是很理解啊

一般的思路就是，我们需要求大区间的最优解，那么我可以把这个大区间分隔成一个个小区间，找出每个小区间的最优解，然后将这一个个小区间进行合并，得到大区间的最优解。

一般的情况下，是通过枚举区间的长度$len$，作为阶段，然后得到一个区间的$l$和$r$，作为状态，然后在这个区间中枚举分隔点$k$，取得最优解。

for (int len = 2; len <= n; len++) {
		for (int i = 1; i <= n - len + 1; i++) {
			int j = i + len - 1;
			for (int k = i; k < j; k++) {
				dpm[i][j] = min(dpm[i][j], dpm[i][k] + dpm[k + 1][j] + c[j] - c[i - 1]);
				dpM[i][j] = max(dpM[i][j], dpM[i][k] + dpM[k + 1][j] + c[j] - c[i - 1]);
			}
		}
	}

四边形优化

自己不是很会四边形优化，就不怎么详细讲解了。

详细讲解点这里。

就讲一下我稍微懂的一点吧，以后再补吧，真的dp不能足够的理解，就很头痛。

如果需要证明四边形优化是否成立的话，可以使用打表的形式，观察是否$p[i][j-1]\leq p[i][j]\leq p[i+1][j]$。

如果成立便可以使用四边形优化。

对石子合并来说的，最小值可以使用四边形优化，但是最大值不能。

这里贴一下模板吧。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cstring> 
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 2e3 + 9;
const int mod = 1e6 + 3;
int dpmin[maxn][maxn], n, a[maxn], dpmax[maxn][maxn], sum[maxn], kma[maxn][maxn], kmi[maxn][maxn];
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	met(dpmin, oo);
	_rep(i, 1, n)
	{
		cin >> a[i];
		a[i + n] = a[i];
		dpmin[i][i] = dpmin[i + n][i + n] = 0;
	}
	_rep(i, 1, 2 * n) {
		sum[i] = sum[i - 1] + a[i];
		kmi[i][i] = kma[i][i] = i;
	}
	_rep(len, 2, n)
	{
		_rep(l, 1, 2 * n - len + 1)
		{
			int r = l + len - 1;
			_rep(k, l, r - 1) {
				/*dpmax[l][r] = max(dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1], dpmax[l][r]);
				dpmin[l][r] = min(dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1], dpmin[l][r]);*/
				if (dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1] > dpmax[l][r]) {
					dpmax[l][r] = dpmax[l][k] + dpmax[k + 1][r] + sum[r] - sum[l - 1];
					kma[l][r] = k;
				}
				if (dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1] < dpmin[l][r]) {
					dpmin[l][r] = dpmin[l][k] + dpmin[k + 1][r] + sum[r] - sum[l - 1];
					kmi[l][r] = k;
				}
			}
		}
	}
	_rep(i, 1, n + 1) {
		_rep(j, i+1, i + n-1) {
			//assert(kma[i][j - 1] <= kma[i][j] && kma[i][j] <= kma[i + 1][j]);
			//assert(kmi[i][j - 1] <= kmi[i][j] && kmi[i][j] <= kmi[i + 1][j]);
			printf("kma[%d][%d]=%d <= kma[%d][%d]=%d <= kma[%d][%d]=%d ",i,j-1,kma[i][j-1],i,j,kma[i][j],i+1,j,kma[i+1][j]);
			if(kma[i][j - 1] <= kma[i][j] && kma[i][j] <= kma[i + 1][j])	cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
	}
	cout<<endl<<endl;
	_rep(i, 1, n + 1) {
		_rep(j, i+1, i + n-1) {
			//assert(kma[i][j - 1] <= kma[i][j] && kma[i][j] <= kma[i + 1][j]);
			//assert(kmi[i][j - 1] <= kmi[i][j] && kmi[i][j] <= kmi[i + 1][j]);
			printf("kmi[%d][%d]=%d <= kmi[%d][%d]=%d <= kmi[%d][%d]=%d ",i,j-1,kmi[i][j-1],i,j,kmi[i][j],i+1,j,kmi[i+1][j]);
			if(kmi[i][j - 1] <= kmi[i][j] && kmi[i][j] <= kmi[i + 1][j])	cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
	}
}

对于最大值来说，他区间$[i,j]$的最大值，等于区间$[i,j−1]$和$[i+1,j]$中的最大值加上$w(i,j)$。

因为区间$[i+1,j-1]$的最大值是相同的，只需要看先合并左边还是先合并右边了，取其中的最大值。

典型例题

洛谷-P1880 石子合并

题目大意

有一圈石子，你需要把他们合成一堆，求最小花费和最大花费。

解题思路

模板题。

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 310, INF = 1e9;
int dpm[N][N],dpM[N][N], p[N], num[N], c[N];

int main() {
	int n;
	cin >> n;
	memset(dpm, 127, sizeof(dpm));
	memset(dpM, 0, sizeof(dpM));
	for (int i = 1; i <= n; i++) cin >> num[i],num[i+n] = num[i];
	for (int i = 1; i <= 2 * n; i++) c[i] = c[i - 1] + num[i], dpm[i][i] = 0, dpM[i][i] = 0;
	for (int len = 2; len <= n; len++) {
		for (int i = 1; i <= 2*n - len + 1; i++) {
			int j = i + len - 1;
			for (int k = i; k < j; k++) {
				dpm[i][j] = min(dpm[i][j], dpm[i][k] + dpm[k + 1][j] + c[j] - c[i - 1]);
				dpM[i][j] = max(dpM[i][j], dpM[i][k] + dpM[k + 1][j] + c[j] - c[i - 1]);
			}
		}
	}
	int ans1 = 1e9, ans2 = 0;
	for (int i = 1; i <= n; i++) {
		ans1 = min(ans1, dpm[i][i + n - 1]);
		ans2 = max(ans2, dpM[i][i + n - 1]);
	}
	cout << ans1 << endl;
	cout << ans2 << endl;
}