1． 石子合并

在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(<=20)。

选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；

输入数据：

第一行为石子堆数n；

第二行为每堆的石子数,每两个数之间用一个空格分隔。

输出数据：

从第一至第n行为得分最小的合并方案。第n+1行是空行.从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。

Sample Input

4

4 5 9 4

Sample Output

－4 5 9 －4

－8 －5 9

－13 －9

22

4 －5 －9 4

4 －14 －4

－4 －18

22

#include<iostream.h>
void main()
{
int a[101],b[101],c[101],d[101];
int m[101][101],i,j,k,t,n,min,max;
cin>>n;
t=n;
for(i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
for(i=0;i<n;n--) //求最小得分方法
{
if(n==1)
{
cout<<a[0]<<" "<<endl;
break;
}
for(j=0;j<n;j++)
{
if(n==2)
{
m[0][1]=a[0]+a[1];
break;
}
else
m[j][(j+1)%n]=a[j]+a[(j+1)%n];
}
min=m[0][1];
for(j=0;j<n;j++)
{
if(n!=2)
{
if(min>m[j][(j+1)%n])
min=m[j][(j+1)%n];
}
else
break;
}
for(j=0;j<n;j++)
{
if(n==2)
{
a[0]=-1*a[0];
a[1]=-1*a[1];
break;
}
else
if(min==m[j][(j+1)%n])
{
a[j]=-1*a[j];
a[(j+1)%n]=-1*a[(j+1)%n];
}
}
for(k=0;k<n;k++) //输出一次合并的结果
{
cout<<a[k]<<" ";
}
a[(j++)%n]=min;
for(j=0,k=0;k<n;k++)
{
if(a[k]>0)
{
c[j]=a[k];
j++;
}
}
for(k=0;k<j;k++)
a[k]=c[k];
cout<<endl;
}
for(i=0;i<t;t--) //求最大得分方法
{
if(t==1)
{
cout<<b[0]<<" "<<endl;
break;
}
for(j=0;j<t;j++)
{
if(t==2)
{
m[0][1]=b[0]+b[1];
break;
}
else
m[j][(j+1)%t]=b[j]+b[(j+1)%t];
}
max=m[0][1];
for(j=0;j<t;j++)
{
if(t!=2)
{
if(max<m[j][(j+1)%t])
max=m[j][(j+1)%t];
}
else
break;
}
for(j=0;j<t;j++)
{
if(t==2)
{
b[0]=-1*b[0];
b[1]=-1*b[1];
break;
}
else
if(max==m[j][(j+1)%t])
{
b[j]=-1*b[j];
b[(j+1)%t]=-1*b[(j+1)%t];
break;
}
}
for(k=0;k<t;k++)
{
cout<<b[k]<<" ";
}
b[(j++)%t]=max;
for(j=0,k=0;k<t;k++)
{
if(b[k]>0)
{
d[j]=b[k];
j++;
}
}
for(k=0;k<j;k++)
b[k]=d[k];
cout<<endl;
}
}

首先说一下 用回溯肯定超时 回溯=穷举 与之相似的乘法问题 在穷举时时间复杂度达到30!
所以应考虑DP 但是在网上有人说 即使用DP也不行
我将完成之后将代码上传

是DP问题
一般的复杂度为O(N^3);N=100的时候是可以过的

这个问题可以用四边形不等式优化到O(n^2),只是具体怎么做我现在还不理解