原题

题目描述

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

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

输入格式

数据的第 1 行是正整数 N，表示有 N 堆石子。

第 2 行有 N 个整数，第 i 个整数 ai​ 表示第 i 堆石子的个数。

输出格式

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

输入输出样例

输入 #1

4
4 5 9 4

输出 #1

43
54

题解（搬运自我好久好久之前在洛谷发的博客）

（顺便做个博客文章格式的测试）

（大佬轻喷）

《信息学奥赛一本通–提高篇》给了一个非常优秀的O(8n3)的代码

作为蒟蒻我表示看不懂

难受

不过没关系

蒟蒻有蒟蒻的dp方法

淡定地枚举了区间长度,然后一层一层增加

一段一段地维护**（不懂的可以手动看代码模拟）**

然后，默默地祭出了O(2n3)的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int a[201],sum[201];
int Fmin[201][201],Fmax[201][201];
inline int read()//读入优化大法好！！！
{
	int res=0;
	char ch=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
int main()
{
	int n=read();
    //把环拉成一条2*n的线
	for(int i=1;i<=n;++i)a[i]=a[i+n]=read();
	for(int i=1;i<=2*n;++i)sum[i]=sum[i-1]+a[i];
	memset(Fmin,127/3,sizeof(Fmin));//取最小值需要一点放大的初值
	for(int i=1;i<=2*n;++i)Fmin[i][i]=0;//这个不改会炸的！！！
	for(int l=1;l<n;++l)//枚举区间长度1到n-1
		for(int i=1;i+l<=2*n;++i)//枚举左端点
			for(int k=i;k<i+l;++k)//这个就不用解释了吧~~~
			{
				Fmin[i][i+l]=min(Fmin[i][i+l],Fmin[i][k]+Fmin[k+1][i+l]+sum[i+l]-sum[i-1]);
				Fmax[i][i+l]=max(Fmax[i][i+l],Fmax[i][k]+Fmax[k+1][i+l]+sum[i+l]-sum[i-1]);
			}
	int ansmin=923917391,ansmax=0;
    //然后开个O(2n)求最终答案（因为把环拉成链了）
	for(int i=1;i<n;++i)ansmin=min(ansmin,Fmin[i][i+n-1]);
	for(int i=1;i<n;++i)ansmax=max(ansmax,Fmax[i][i+n-1]);
	printf("%d\n",ansmin);
	printf("%d\n",ansmax);
	return 0;
}

~~然后，常数其实也没有2那么大啦~~~时间复杂度具体怎么算我也不知道

估计一下时间复杂度差不多只有O(n3)