欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

DP(优化专题-四边形不等式优化一)

程序员文章站 2022-04-01 18:42:28
...

题意: 有若干堆石子围成一圈儿, 每合并两堆石子, 就对答案贡献了这两堆石子的重量, 现询问答案的最大值与最小值.

>> face <<

状态: dpmin[l][r]→dpmin[l][r]\to该区间内的最小收益,dpmax[l][r]→dpmax[l][r]\to该区间内最大收益

目标:dpmin[1][n]&amp;dpmax[1][n]dpmin[1][n] \&amp; dpmax[1][n]

边界: 第一次转移的贡献全由石堆提供. 不需要额外提供边界(记忆化搜索),针对区间最小,首先要memset(dpmin, ∞\infty, sizeof(dpmin)), 然后确保dpmin[i][i]=0,i∈[1,2∗n]dpmin[i][i] = 0,i\in[1, 2*n]

合法判断: 本题无

转移方程: 区间dp, 枚举未知, 让所有能转移到该未知的状态来转移

{dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r])+∑i=li≤ra[i];dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r])+∑i=li≤ra[i]; \begin{dcases} dpmin[l][r] = min(dpmin[l][r], dpmin[l][k] + dpmin[k+1][r]) + \sum_{i = l}^{i \leq r} a[i];\\[2ex] dpmax[l][r] = max(dpmax[l][r], dpmax[l][k] + dpmax[k+1][r]) + \sum_{i = l}^{i \leq r} a[i]; \end{dcases}

attention: 圆环链化 (化为长度为2*n的链)

双倍经验:

Strategy:区间dp(用四边形不等式优化)

先贴一波大佬的博客

  • 若想用四边形不等式优化必须满足 决策单调性, 就本题而言, 针对dpmin[i][j]都有某最K值使得该最小值被取到, 而且, 该最小值是和决策区间[i][j]有非严格单调关系的情况, 那么我们就可以用一个二维数组存下来, 然后循环找k的时候可以优化一层

首先给出正确的O(n3)O(n^3)代码

#include <bits/stdc++.h>
#include <bits/extc++.h>
#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];
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];
	}
	_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]);
			}
		}
	}

	int min_val = oo, max_val = 0;

	_rep(i, 1, n)
	{
		min_val = min(dpmin[i][i + n - 1], min_val);
		max_val = max(max_val, dpmax[i][i + n - 1]);
	}
	cout << min_val << endl
		 << max_val << endl;
}

然后打表判断决策单调性

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cassert>
#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]);
		}
	}
}

发现只有kmi满足决策单调性, 而kma不满足

但是对于dpmax有一个性质, 对于某dpmax[l][r], 只有k = l或者k = r-1时最大

其实最小也有性质, 当k在l和r中间的时候也能取最小

优化后代码

#include <bits/stdc++.h>
#include <bits/extc++.h>
#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], s[maxn][maxn] ; //s[i][j]存储dpmin[i][j]的最优解k
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];
		s[i][i] = i;
	}
	_rep(len, 2, n)
	{
		_rep(l, 1, 2 * n - len + 1)
		{
			int r = l + len - 1;
			dpmax[l][r] = max(dpmax[l+1][r]+dpmax[l][l], dpmax[l][r-1]+dpmax[r][r]) + sum[r] - sum[l-1];
			int K, tmp = oo;
			_rep(k, s[l][r-1], s[l+1][r]){
				int tt = dpmin[l][k] + dpmin[k+1][r] + sum[r] - sum[l-1];
				if(tt < tmp){
					tmp = tt;
					K = k;
				}
			}
			s[l][r] = K;
			dpmin[l][r] = tmp;
		}
	}
	

	int min_val = oo, max_val = 0;

	_rep(i, 1, n)
	{
		min_val = min(dpmin[i][i + n - 1], min_val);
		max_val = max(max_val, dpmax[i][i + n - 1]);
	}
	cout << min_val << endl
		 << max_val << endl;
}
相关标签： 四边形不等式 dp

上一篇： 蓝桥杯 算法提高-合并石子(区间dp)

下一篇： 四边形填充

推荐阅读