题目描述

将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最小。

输入格式

输入第一行一个整数 $n$，表示有 $n$ 堆石子。

第二行 $n$ 个整数，表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

样例

4
4 5 9 4

43
54

数据范围与提示

对于 $100\%$ 的数据，有 $1\le n \le 200$。

#include<bits/stdc++.h>
using namespace std;

const int N = 405;  // 由于是环形且最多n=200，开2倍空间405足够
int n, a[N], s[N];  // a[]存储石子数量，s[]存储前缀和
int f1[N][N], f2[N][N];  // f1[i][j]表示合并区间[i,j]的最大得分，f2[i][j]表示最小得分

int main(){
	// 初始化最小得分数组为极大值（0x3f3f3f3f）
	memset(f2, 0x3f, sizeof f2);  
	
	cin >> n;  // 输入石子堆数量
	// 读入n堆石子，并复制一份到后面（处理环形结构：将环形转为线性）
	for(int i = 1; i <= n; ++ i) cin >> a[i], a[i + n] = a[i];
	
	// 计算前缀和数组，方便快速计算区间和
	for(int i = 1; i <= 2 * n; ++ i){
		s[i] = s[i - 1] + a[i];
	}
	
	// 枚举区间长度（从1到n，因为最多合并n堆）
	for(int len = 1; len <= n; ++ len){
		// 枚举区间起点i，计算终点j = i + len - 1（确保j在2n范围内）
		for(int i = 1, j; (j = i + len - 1) < 2 * n; ++ i){
			// 长度为1的区间无法合并，合并代价为0
			if(len == 1) f2[i][j] = 0;
			
			// 枚举分割点k，将区间[i,j]分为[i,k]和[k+1,j]
			for(int k = i; k < j; ++ k){
				// 最大得分：取两种分割方式的最大值，加上当前区间的石子总和（合并代价）
				f1[i][j] = max(f1[i][j], f1[i][k] + f1[k + 1][j] + s[j] - s[i - 1]);
				// 最小得分：取两种分割方式的最小值，加上当前区间的石子总和（合并代价）
				f2[i][j] = min(f2[i][j], f2[i][k] + f2[k + 1][j] + s[j] - s[i - 1]);
			}
		}
	}
	
	// 寻找长度为n的区间中最小和最大的合并代价（环形结构的所有可能起点）
	int ans1 = 1e9, ans2 = 0;  // ans1存储最小得分，ans2存储最大得分
	for(int i = 1; i <= n; ++ i){
		ans1 = min(ans1, f2[i][i + n - 1]);  // 区间[i, i+n-1]是长度为n的连续区间
		ans2 = max(ans2, f1[i][i + n - 1]);
	}
	
	// 输出结果
	cout << ans1 << endl << ans2;
	return 0;
}