我们简单看一下题目，要我们合并石子，很容易想到的结论就是两堆石子数目小的话合并所需的得分就小，两堆石子数目大的话合并所需要的得分就大，这里可能容易跟另一道名叫“合并果子”的著名贪心题目搞混，这里注意一下，由于我们是每次合并的时候只能使用相邻的两堆石子，跟他们的相对顺序有关，贪心很显然是错的，因此这道题目我们使用动态规划来解决。

对于一个第 L 堆石子到第 R 堆石子，我们考虑这堆石子的合并所需要的最小的分从何而来。很显然，L~R这堆石子的最小得分一定是从这个区间中两个某子区间的最小得分转移而来，因此我们可以考虑枚举这两个子区间，这样一来我们可以得到下面的方程式：

我们设 $f_{l,r}$ 表示第 $l$ 堆石子到第 $r$ 堆石子的最小得分，我们枚举子区间的分割点 $k$ ，那么有:

f_{l,r} = \min({f_{l,k} + f_{k+1,r} + l 到 k 的石子数 + (k+1) 到 r 的石子数})

上面的式子就是我们本题的状态转移方程式,最后 $f_{1,n}$ 就是答案，求最大值的话就是 min 改成 max 就行了，~~但是本题难点不在于这个（~~，我们还有两个悬而未决的问题：

转移的顺序如何确定
题目中说的是圆形操场，因此这堆石子其实是一个环，即第 1 堆石子可以和第 n 堆合并

先解决第一个问题，我们可以想象一下，对于一个大区间，他肯定是从两个比它小的区间转移而来，因此我们要按区间长度从小到大计算。

其实对于这类转移顺序不好确定问题，我们可以使用记忆化搜索的形式来编写代码，可以巧妙的规避这个问题。

我们要枚举 l,r,k同时还要计算区间和,每一个计算都要o(n)的时间复杂度，因此我们总的时间复杂度是 $O(n^4)$ ，~~包超时的老弟~~,我们可以使用前缀和来优化掉 O(n) 的区间求和，这样我们的时间复杂度就可以到 $O(n^3)$ ，这样就不会超时。

代码如下(非记忆化搜索),对应"洛谷P1775 石子合并（弱化版）"

# code by 陈新茹
MAXN = 1005
f = [[9999999999] * MAXN for i in range(MAXN)]
n = int(input())
m = list(map(int,input().split()))
m.insert(0,0)
# 算代价
s = [0] * (n + 10)
for i in range(1,n+1):
    s[i] = s[i-1] + m[i]
def sum(l,r):
    return s[r] - s[l-1]

for i in range(1,n+1):
    f[i][i] = 0
for length in range(1,n+1):
    for l in range(1,n-length+2):
        r = l + length - 1
        for mid in range(l,r):
            f[l][r] = min(f[l][r],sum(l,r) + f[l][mid] + f[mid + 1][r])
print(f[1][n])

标准版（考虑环）

上面是这个题目的弱化版的代码，接下来我们考虑如何将这个区间变成环，一个很简单的做法 ~~（但是不好想）~~ 就是我们将原始的石子复制两遍让他们首尾相接，之后正常转移，最后在1~2n的区间中寻找长度为 n 的石子最优解就可以了。

代码如下

# code by 陈新茹
MAXN = 1005
f = [[9999999999] * MAXN for i in range(MAXN)]
g = [[0] * MAXN for i in range(MAXN)]
n = int(input())
a = list(map(int,input().split()))
# 算代价
for i in range(n):
    a.append(a[i])
a.insert(0,0)
s = [0] * (2 * n+ 10)
for i in range(1,2 * n+1):
    s[i] = s[i-1] + a[i]
def sum(l,r):
    return s[r] - s[l-1]

for i in range(1,2 * n+1):
    f[i][i] = 0
    g[i][i] = 0
for length in range(1,n+1):
    for l in range(1,2 * n-length+2):
        r = l + length - 1
        for mid in range(l,r):
            f[l][r] = min(f[l][r],sum(l,r) + f[l][mid] + f[mid + 1][r])
            g[l][r] = max(g[l][r], sum(l, r) + g[l][mid] + g[mid + 1][r])
min_ans = 999999
max_ans = 0
for i in range(0, n+1):
    min_ans = min(min_ans, f[1+i][n+i])
    max_ans = max(max_ans, g[1+i][n+i])
print(str(min_ans) + "\n" + str(max_ans))

下面放一下另一种写法，C++版的记忆化搜索版代码

// code by 刘喆
#include<algorithm>
#include<iostream>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans1,ans2;
int a[205],f1[205][205],f2[205][205];
int dp1(int L,int R) {
	if(f1[L][R])return f1[L][R];
	if(L==R)    return f1[L][R]=0;
	int res=INF;
	for(int k=L; k<R; k++)
		res=min(res,dp1(L,k)+dp1(k+1,R)+a[R]-a[L-1]);
	return f1[L][R]=res; }
int dp2(int L,int R) {
	if(f2[L][R])return f2[L][R];
	if(L==R)    return f2[L][R]=0;
	int res=0;
	for(int k=L; k<R; k++)
		res=max(res,dp2(L,k)+dp2(k+1,R)+a[R]-a[L-1]);
	return f2[L][R]=res; }
int main() {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		a[i+n]=a[i]; }
	for(int i=1; i<=2*n; i++)
		a[i]+=a[i-1];
	dp1(1,2*n);
	dp2(1,2*n);
	ans1=INF;
	ans2=0;
	for(int i=1; i<=n; i++) {
		ans1=min(f1[i][n+i-1],ans1);
		ans2=max(f2[i][n+i-1],ans2); }
	cout<<ans1<<endl<<ans2;
	return 0; }