在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
输入:
4(石子的堆数)
4 4 5 9(每一堆的石子数目)
输出:
43 54
我们知道链式的石子合并问题是相邻两堆之间可以合并,那么环形的和链式的区别就在于,环形的相当于是链式的头尾两堆也能合并
那么,我们只要解决,如何在链式的基础上更换每次头和尾的问题即可,即环形的切割点
n堆,有n个切割点,每次以区间长度为n的链式的进行求解。
如果想n个切割点,每次长度为n,那么我们创建长度为2*n的数组,存放两次石子序列即可。
和链式一样,合并两堆的代价最小
即把当前的链式区间划分,左+右+合并左右 的代价达到最优即可
int f[2 * n + 1][2 * n + 1]; //计算合并的最小值 f[i][j]表示i到j这个范围内合并的代价
int g[2 * n + 1][2 * n + 1]; //计算合并的最大值 g[i][j]表示i到j这个范围内合并的代价
#include <iostream> #include<cstring> using namespace std; //每次选取相邻的两堆合并 环形可以开2*n大小的数组,然后以n为区间进行求值 //最优子问题:求解每小个区间(以k为分割点,左右还有合并左右的代价 //这里计算合并左右的代价可以利用前缀和的方法 s[r]-s[l-1] #define Max 10005 #define N 410 int MAX(int a,int b){ return a>b?a:b; } int MIN(int a,int b){ return a<b?a:b; } int main() { int n; cin >> n; int a[2 * n + 1] = {}; int f[2 * n + 1][2 * n + 1]; //计算合并的最小值 f[i][j]表示i到j这个范围内合并的代价 int g[2 * n + 1][2 * n + 1]; //计算合并的最大值 g[i][j]表示i到j这个范围内合并的代价 memset(f,Max,sizeof(f)); memset(g,-Max,sizeof(g)); int s[2 * n + 1] = {}; for (int i = 1; i < n + 1; i++) { cin >> a[i]; a[i + n] = a[i]; } for (int i = 1; i <= 2 * n; i++) { //计算前缀和 s[i] = s[i - 1] + a[i]; f[i][i]=0; g[i][i]=0; } //状态计算 for (int len = 2; len <= n; len++) { //区间划分 for(int l=1;l+len-1<=2*n;l++){//左右 int r=l+len-1; for(int k=l;k<r;k++){ //选择区间分割点 f[l][r]=MIN(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]); g[l][r]=MAX(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]); } } } int min=Max,max=-Max; for(int i=1;i<=n;i++){ min=MIN(min,f[i][i+n-1]); max=MAX(max,g[i][i+n-1]); } cout<<min<<" "<<max<<endl; }