洛谷 P1880 [NOI1995]石子合并 ----环形区间dp

题目描述

在一个圆形操场的四周摆放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

题目分析

一开始我脑子里的构图是这样的
这样做的话，不仅区间的总石子数量难算，而且也不知道距离怎么设置了。然后看了一下洛谷大神们的题解，一下明悟。

所以我们可以设置两倍的长度来存放石子数目，距离也可以正常设置了。

实现代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f	//用来设置个最大值
#define SIZE 200+10		//最大数据量100的两倍
using namespace std;

int s[SIZE];			//存放石子
int sum[SIZE];			//存放从1开始的总石子数
int mindp[SIZE][SIZE];	
int maxdp[SIZE][SIZE];

inline int getSum(int i, int j) {	
	return sum[j] - sum[i - 1];		//得到[i, j]区间的总石子数，因为距离<n,所以不会有重复计算的石子
}

void countSum(int n) {				//计算从1开始的总石子数
	sum[1] = s[1];
	for (int i = 2; i <= 2 * n; i ++ ) {
		sum[i] = sum[i - 1] + s[i];
	}
}

int main() {
	memset(mindp, INF, sizeof(mindp));
	memset(maxdp, -1, sizeof(maxdp));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i + n] = s[i];
		mindp[i][i] = maxdp[i][i] = mindp[i + n][i + n] = maxdp[i + n][i + n] = 0;
	}
	countSum(n);
	for (int dis = 1; dis < n; dis++) {			//距离最大为长度 - 1，不可能同一个点到同一个点
		for (int i = 1, j = i + dis; j < (n + n) && i < (n + n) ; i++, j = i + dis) {
			for (int k = i; k < j; k++) {
				mindp[i][j] = min(mindp[i][j], mindp[i][k] + mindp[k + 1][j] + getSum(i, j));
				maxdp[i][j] = max(maxdp[i][j], maxdp[i][k] + maxdp[k + 1][j] + getSum(i, j));
			}
		}
	}
	int minans = INF;
	int maxans = -1;
	for (int i = 1; i <= n; i++) {
		minans = min(minans, mindp[i][n + i - 1]);
		maxans = max(maxans, maxdp[i][n + i - 1]);
	}
	cout << minans << endl;
	cout << maxans << endl;
	return 0;
}