将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。
请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算:
- 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。
- 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。
输入格式
第一行包含整数 $n$,表示共有 $n$ 堆石子。
第二行包含 $n$ 个整数,分别表示每堆石子的数量。
输出格式
输出共两行:
第一行为合并得分总和最小值,
第二行为合并得分总和最大值。
数据范围
$1 \le n \le 200$
输入样例:
4
4 5 9 4
输出样例:
43
54
思路
和线性石子合并不一样的是这里的区间长度应该是2*n 因为可能会用到a[i + n]
因为石子合并之后是个环形的,也就是会出现1234 1234的情况我们需要将数组开大一倍储存链尾,然后就是区间求和一般都用前缀和。
当区间长度为1的时候 无法合并 价值 = 0;
设方程g[l][r]在[l ,r]区间石子合并后的价值最大的合并方案集合
设方程f[l][r]在[l ,r]区间石子合并后的价值最小的合并方案集合
从集合的最后一个不同点出发写出方程
因此枚举分段点k
f[l][r] = f[l][k] + f[k + 1][r] + s[r] - s[l - 1]
g[l][r] = g[l][k] + f[k + 1][r] + s[r] - s[l - 1]
由于本题没有规定区间范围因此需要循环的找一下在【l — l + n - 1】的范围内最小和最大的价值
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=1e3+10;
int arr[N];
int s[N];
int f[N][N];
int g[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];arr[i+n]=arr[i];
}
memset(g,-0x3f,sizeof g);
memset(f,0x3f,sizeof f);
for(int i=1;i<=2*n;i++)s[i]=s[i-1]+arr[i];
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=2*n;l++){
int r=l+len-1;
if(len == 1)g[l][l]=f[l][l]=0;
else {
for(int k=l;k<r;k++){
g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
}
}
int ma=0;
int mi=0x3f3f3f3f;
for(int i=1;i<=n;i++){
ma=max(g[i][i+n-1],ma);
mi=min(f[i][i+n-1],mi);
}
cout<<mi<<endl;
cout<<ma<<endl;
}