此题有直线，圆形两种问法。 分别有最大得分最小得分解法。简单的dp。
直线最大得分
【算法设计与分析习题3-3 石子合并问题直线排列最大得分】#include
#include
using namespace std;
int main()
{
freopen("in.txt","r",stdin);
int n;
cin>>n;
int a[100],m[100][100];
for(int i=1;
i<=n;
i++)
{
cin>>a[i];
}
for(int i=2;
i<=n;
i++)
{
a[i]=a[i]+a[i-1];
}
//默认初始化m[i][i]=0，可以理解为初始的每一堆不合并则得分为0
for(int r=2;
r<=n;
r++)
{
for(int i=1;
i<=n-r+1;
i++)
{
int j=i+r-1;
if(m[i+1][j]>m[i][j-1])//m[i][j]表示从i到j的最大得分，因为只能相邻合并，所以有两种情况，m[i][i]与m[i+1][j]或m[i][j-1]与m[j][j]
m[i][j]=m[i+1][j]+a[j]-a[i-1];
else
m[i][j]=m[i][j-1]+a[j]-a[i-1];
}
}
cout<
}
