题目描述
在一个圆形操场的四周摆放 \(N\) 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 \(2\) 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法，计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。
输入格式
数据的第 \(1\) 行是正整数 \(N\)，表示有 \(N\) 堆石子。
第 \(2\) 行有 \(N\) 个整数，第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆石子的个数。
输出格式
输出共 \(2\) 行，第 \(1\) 行为最小得分，第 \(2\) 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4
样例输出 #1
43
54
提示
\(1\leq N\leq 100\)，\(0\leq a_i\leq 20\)。
思路分析
我们可以使用区间 dp 来解决这道题。我们可以设 \(dp_{l,r}\) 表示合并区间 \((l,r)\) 的石子成一堆所得到的最小得分或最大得分，每一堆肯定是由两堆合并而成的，而这两堆可能是哪些呢？我们可以枚举是哪两堆，枚举中间结点 \(k\)，将 \((l,r)\) 区间分割成 \((l,k)\) 和 \((k+1,r)\) 两个子区间，这样我们便得到了一个动态转移方程：
\(dp_{l,r}=\min(dp_{l,r},dp_{l,k}+dp_{k+1,r}+sum_{l,r});\)
\(dp_{l,r}=\max(dp_{l,r},dp_{l,k}+dp_{k+1,r}+sum_{l,r});\)
其中，\(sum_{l,r}\) 的意思是区间 \((l,r)\) 的和，表示本次合并的分数，加入动规数组中，\(dp_{l,k}+dp_{k+1,r}\) 则表示两个子区间的最小或最大得分，最后对两个区间 dp 数组求 \(\min\) 或 \(\max\) 即可。
注意，因为操场是圆形的，我们需要在 \(a\) 数组后再增加一个 \(a\)，以方便计算，模拟圆。
具体思路详见注释。
\(\texttt{code}\)
/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
int n;
int a[205],dpmin[205][205],dpmax[205][205],sum[205];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(dpmin,0x3f,sizeof(dpmin));//求最小，记得赋最大值
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dpmin[i][i]=0;
sum[i]=sum[i-1]+a[i];//前缀和
}
for(int i=1;i<=n;i++){//增加一倍 a
dpmin[i+n][i+n]=0;
sum[i+n]=sum[i+n-1]+a[i];
}
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++){//枚举中间结点
dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r]+sum[r]-sum[l-1]);
dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r]+sum[r]-sum[l-1]); //如上动态转移方程
}
}
}
int ans1=1e9,ans2=0;
for(int i=1;i<=n;i++){
ans1=min(ans1,dpmin[i][i+n-1]);
ans2=max(ans2,dpmax[i][i+n-1]);
}//每个区间的结果取 min 或 max
cout<<ans1<<"\n"<<ans2;
return 0;
}