原题

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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)