洛谷P1880 石子合并

题目描述

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式

输入格式：

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式：

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入样例#1：

4
4 5 9 4

输出样例#1：

43
54

今天写加分二叉树的时候发现了一个神奇的玩意——四边形优化。虽然久仰大名，却从未写过的我怀着一丝好奇心学习了一下。简而言之，就是区间dp数组在满足一定的条件后，最优方案的下标会呈现单调性。因此可以用前面推出的最优方案下标来限制当前的最优方案枚举范围，从而达到优化。但是我实在太菜了，看不懂证明。这一篇博客就讲解的比较全面：我是“这篇博客”

首先对于环形问题，我们可以先拆环成链。然后再对每一个长度为n的区间进行dp。注意到这样的方法会重复做很多次无用dp，因此我们用普通的区间dp对整体的一条链dp，限制区间长度为n以内。另外，这道题需要先做前缀和。

那么我们写一下状态转移方程：

最大值：dpmx[l][r] = max{dpmx[l][k] + dpmx[k + 1][r] + sum[l][r]}

最小值：dpmn[l][r] = min{dpmn[l][k] + dpmn[k + 1][r] + sum[l][r]}

发现的二个方程可以优化，注意到对于sum[i][j]，有sum[i][j] +sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j]。并且，很明显，sum[i][j] <= sum[i-1][j+1]的（不可能有负数个石子）。那么就可以使用四边形优化了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 205;
int mx, mn, pref[maxn], dpmx[maxn][maxn], dpmn[maxn][maxn], smn[maxn][maxn], n, l, r;
int main() {
	memset(dpmn, 0x3f, sizeof(dpmn)), mn = 0x3f3f3f3f;
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) 
		scanf("%d", &pref[i]), dpmn[i + n][i + n] = dpmn[i][i] = 0, pref[i + n] = pref[i];
	for(register int i = 1; i <= (n << 1) - 1; ++i)
		smn[i][i] = i;
	for(register int i = 1; i <= (n << 1) - 1; ++i) 
		pref[i] += pref[i - 1];
	for(register int i = 1; i <= n; ++i)
    	for(register int j = 1; j <= (n << 1) - i - 1; ++j) {
    		l = j, r = i + j;
    		for(register int k = l; k <= r - 1; ++k) {
    			if(dpmx[l][r] < dpmx[l][k] + dpmx[k + 1][r] + pref[r] - pref[l - 1])
    				dpmx[l][r] = dpmx[l][k] + dpmx[k + 1][r] + pref[r] - pref[l - 1];
    		}	
    		for(register int k = smn[l][r - 1]; k <= smn[l + 1][r]; ++k) {
				if(dpmn[l][r] > dpmn[l][k] + dpmn[k + 1][r] + pref[r] - pref[l - 1])
    				dpmn[l][r] = dpmn[l][k] + dpmn[k + 1][r] + pref[r] - pref[l - 1], smn[l][r] = k;
			}
		}
	for(register int i = 1; i <= n; ++i) {
			mx = max(dpmx[i][i + n - 1], mx);
			mn = min(dpmn[i][i + n - 1], mn);
		}
	printf("%d\n%d", mn, mx);
	return 0;
}

Rockdu's Blog