题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1： 复制
4
4 5 9 4
输出样例#1： 复制
43
54 *****石子合并分为两个梯度的形式
第一种就是一条线那样的石子合并
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int i,j,l,k,n,a[],f[][],s[];
int main()
{
scanf("%d",&n);
s[] = ;
for(i = ;i <= n;i++)
{
scanf("%d",&a[i]);
s[i] = s[i - ] + a[i];
}
for(l = ;l <= n;l++)
{
for(i = ;i <= n + l - ;i++)
{
j = i + l - ;
for(k = i;k <= j - ;k++)
{
if(f[i][j] != )
f[i][j] = min(f[i][j],f[i][k] + f[k + ][j] + s[j] - s[i - ]);
else
f[i][j] = f[i][k] + f[k + ][j] + s[j] - s[i - ];
}
}
}
printf("%d",f[][n]);
return ;
}
第二种是围成一个圈那样，和这道题就是这个类型
O（N^3)有两种算法
第一种就是
这种啊博主也没怎么看懂，等着2020年6月9号看吧吼吼
下面这种博主还是会滴
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int i,j,m,n,l,k,da = ,an = ,a[],f[][],s[],p[][];
int main()
{
scanf("%d",&n);
s[] = ;
for(i = ;i <= n;i++)
{
scanf("%d",&a[i]);
a[i + n] = a[i];
}
for(i = ;i <= * n;i++)
{
s[i] = s[i - ] + a[i];
}
for(l = ;l <= n;l++)
{
for(i = ;i <= n * - l;i++)
{
j = i + l - ;
for(k = i;k <= j - ;k++)
{
if(f[i][j] != )
f[i][j] = min(f[i][j],f[i][k] + f[k + ][j] + s[j] - s[i - ]);
else
f[i][j] = f[i][k] + f[k + ][j] + s[j] - s[i - ];
p[i][j] = max(p[i][j],p[i][k] + p[k + ][j] + s[j] - s[i - ]);
}
}
}
for(i = ;i <= n;i++)
{
if(da != )
da = min(da,f[i][i + n - ]);
else
da = f[i][i + n - ];
an = max(an,p[i][i + n - ]);
}
printf("%d\n%d",da,an);
return ;
}