[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 N N N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 2 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分和最大得分。
输入格式
数据的第 1 1 1 行是正整数 N N N，表示有 N N N 堆石子。
第 2 2 2 行有 N N N 个整数，第 i i i 个整数 a i a_i ai 表示第 i i i 堆石子的个数。
输出格式
输出共 2 2 2 行，第 1 1 1 行为最小得分，第 2 2 2 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4
样例输出 #1
43
54
提示
1 ≤ N ≤ 100 1\leq N\leq 100 1≤N≤100， 0 ≤ a i ≤ 20 0\leq a_i\leq 20 0≤ai≤20。
前置弱化版题目，石子合并（洛谷p1775）
做法1
单链复制，破环为链
本质上在时间复杂度没有变化，只是对于环形区间dp的一种做法
为什么长度为n的环可以看做长度为2n的链？
- 因为n堆石子会合并n-1次，就像并查集一样，最后总会刚好有两端是没有连接的，所以计算最大值可以这样算，然后从中选取长度为n且分数最大的一段链。
例： 对于序列 1 2 3 4 1\space2\space3\space4\space 1 2 3 4 ,复制为 1 2 3 4 1\space2\space3\space4\space 1 2 3 4 1 2 3 4 1\space2\space3\space4\space 1 2 3 4 ，前缀和求法不变
方程
d
p
_
m
i
n
[
i
]
[
j
]
=
m
i
n
(
d
p
[
i
]
[
j
]
,
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
s
u
m
[
j
]
−
s
u
m
[
i
−
1
]
)
dp\_min[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
dp_min[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]−sum[i−1])
d
p
_
m
a
x
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
j
]
,
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
s
u
m
[
j
]
−
s
u
m
[
i
−
1
]
)
dp\_max[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
dp_max[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]−sum[i−1])
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=303;
ll f_min[N][N],f_max[N][N],sum[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%lld",&sum[i]),sum[i+n]=sum[i];
memset(f_min,0x3f,sizeof f_min);//注意求f_min需要初始化
for(int i=1;i<=2*n;i++){
f_min[i][i]=0;//与自己合并价值为0
sum[i]+=sum[i-1];//求前缀和，这是一种写法
}
for(int len=2;len<=n;len++)//dp部分，枚举区间长度
{
for(int i=1;i+len-1<=2*n;i++)//枚举左端点
{
int j=i+len-1;//右端点
for(int k=i;k<j;k++)//枚举一个合适的中间点合并
{
f_max[i][j]=max(f_max[i][j],f_max[i][k]+f_max[k+1][j]+sum[j]-sum[i-1]);//求max
f_min[i][j]=min(f_min[i][j],f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1]);//求min，他们的实现原理是相同的，方程也基本相同
}
}
}
ll ansmax=0,ansmin=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)
{
ansmin=min(ansmin,f_min[i][i+n-1]);//寻找长度为n的答案区间
ansmax=max(ansmax,f_max[i][i+n-1]);
}
printf("%lld\n",ansmin);
printf("%lld",ansmax);
return 0;
}
做法2
四边形不等式
这是一种对于部分区间动态规划的优化方法，本蒟蒻讲的不明白，建议去看这个
简单来说，四边形不等式长这样：（w代表区间价值）
对所有
i
<
i
′
<
j
<
j
′
，都有
w
(
i
,
j
)
+
w
(
i
′
,
j
′
)
<
=
w
(
i
,
j
′
)
+
w
(
i
′
,
j
)
对所有i<i'<j<j'，都有w(i,j)+w(i',j')<=w(i,j')+w(i',j)
对所有i<i′<j<j′，都有w(i,j)+w(i′,j′)<=w(i,j′)+w(i′,j)
若满足上述条件，则满足使用四边形不等式的条件
只有满足
w
[
i
]
[
j
]
w[i][j]
w[i][j]是关于 i 和 j 的二元函数时才能讨论单调性和四边形不等式的问题。
定理：
- 如果 w [ i , j ] w[i,j] w[i,j]满足四边形不等式和单调性，则用dp计算dp[][]的时间复杂度是 O ( n 2 ) O(n^2) O(n2)的
- 对于 d p _ m i n [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + s u m [ j ] − s u m [ i − 1 ] ) dp\_min[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]) dp_min[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]−sum[i−1])，如果 w [ i , j ] w[i,j] w[i,j]满足四边形不等式，那么 d p [ i ] [ j ] dp[i][j] dp[i][j]也满足四边形不等式。（dp_max同理）
- 记录 s [ i ] [ j ] s[i][j] s[i][j]为 d p [ i ] [ j ] dp[i][j] dp[i][j]取得最优值时的分割点，如果dp满足四边形不等式，那么 s [ i ] [ j − 1 ] < = s [ i ] [ j ] < = s [ i + 1 ] [ j ] s[i][j-1]<=s[i][j]<=s[i+1][j] s[i][j−1]<=s[i][j]<=s[i+1][j]
使用
看着原理很复杂，但对于求最小值的实现其实很简单，只需要把最后一层循环更改为
s
[
i
]
[
j
−
1
]
<
=
k
<
=
s
[
i
+
1
]
[
j
]
s[i][j-1]<=k<=s[i+1][j]
s[i][j−1]<=k<=s[i+1][j]即可
但是！求最大值不能用四边形不等式，
因为最大值不满足单调性，
但最大值有一个性质，
即总是在两个端点的最大者中取到。
为什么最大值从可以两个端点的最大者取得？
首先可以把最后一步看成两堆石子合并，倒数第二部看成三堆石子中的两堆合并，再与第三堆合并。
那三堆中哪两堆合并呢？
(用w[i]表示第i堆重量)
前两堆:w1=2w[1]+2w[2]+w[3]w1=2w[1]+2w[2]+w[3]
后两堆:w2=w[1]+2w[2]+2w[3]w2=w[1]+2w[2]+2w[3]（自行推导)
所以应该将1号和3号中较大的一堆与第2堆合并，也就是把一堆合并得尽可能大，所以就有
因此对于最大值有以下方程
d
p
_
m
a
x
=
m
a
x
(
d
p
_
m
a
x
[
i
]
[
j
−
1
]
,
d
p
_
m
a
x
[
i
+
1
]
[
j
]
)
+
s
u
m
[
j
]
−
s
u
m
[
i
−
1
]
dp\_max=max(dp\_max[i][j-1],dp\_max[i+1][j])+sum[j]-sum[i-1]
dp_max=max(dp_max[i][j−1],dp_max[i+1][j])+sum[j]−sum[i−1]
注意！求 d p _ m i n dp\_min dp_min时不能直接修改 d p _ m i n [ i ] [ j ] dp\_min[i][j] dp_min[i][j]，因为在更改时会影响循环内的部分值
写法1
for(int len=2;len<=n;len++){
for(int i=2*n-1;i>0;i--){//注意反推，存在f_min[i+1][j]
int j=i+len-1;
int tmp=INF,s_tmp=0;
f_max[i][j]=max(f_max[i][j-1],f_max[i+1][j])+sum[j]-sum[i-1];
for(int k=s_min[i][j-1];k<=s_min[i+1][j];k++){
if(f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1]<tmp){
tmp=f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1];
s_tmp=k;
}
}
s_min[i][j]=s_tmp;
f_min[i][j]=tmp;
}
}
写法2
for(int i=n*2-1;i>0;i--){
for(int j=i+1;j<=n*2;j++){//注意反推，存在f_min[i+1][j]
int tmp=INF,s_tmp=0;
f_max[i][j]=max(f_max[i][j-1],f_max[i+1][j])+sum[j]-sum[i-1];
for(int k=s_min[i][j-1];k<=s_min[i+1][j];k++){
if(f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1]<tmp){
tmp=f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1];
s_tmp=k;
}
}
s_min[i][j]=s_tmp;
f_min[i][j]=tmp;
}
}
完整AC CODE（同样两种写法，本质相同，只是循环有略微的差异）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=303;
const int INF=0x3f3f3f3f;
ll f_min[N][N],f_max[N][N],sum[N];
ll s_min[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
sum[i+n]=sum[i];
}
memset(f_min,0x3f,sizeof f_min);
for(int i=1;i<=2*n;i++){
f_min[i][i]=0;
sum[i]+=sum[i-1];
s_min[i][i]=i;
//s_max[i][i]=i;
}
for(int i=n*2-1;i>0;i--){//写法1
for(int j=i+1;j<=n*2;j++){//注意反推，存在f_min[i+1][j]
int tmp=INF,s_tmp=0;
f_max[i][j]=max(f_max[i][j-1],f_max[i+1][j])+sum[j]-sum[i-1];
for(int k=s_min[i][j-1];k<=s_min[i+1][j];k++){
if(f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1]<tmp){
f_min[i][j]=f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1];
s_min[i][j]=k;
}
}
s_min[i][j]=s_tmp;
f_min[i][j]=tmp;
}
}
/*for(int len=2;len<=n;len++){ //写法2
for(int i=2*n-1;i>0;i--){//注意反推，存在f_min[i+1][j]
int j=i+len-1;
int tmp=INF,s_tmp=0;
f_max[i][j]=max(f_max[i][j-1],f_max[i+1][j])+sum[j]-sum[i-1];
for(int k=s_min[i][j-1];k<=s_min[i+1][j];k++){
if(f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1]<tmp){
tmp=f_min[i][k]+f_min[k+1][j]+sum[j]-sum[i-1];
s_tmp=k;
}
}
s_min[i][j]=s_tmp;
f_min[i][j]=tmp;
}
}*/
ll ansmax=0,ansmin=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)
{
ansmin=min(ansmin,f_min[i][i+n-1]);
ansmax=max(ansmax,f_max[i][i+n-1]);
}
cout<<ansmin<<endl;
cout<<ansmax<<endl;
return 0;
}
做法3 GarsiaWachs
这个算法可以说专为石子合并所生，对本题来说这个算法就相当于大炮打蚊子，
经过平衡树优化后它的时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
使用这个算法解决的石子合并是这个（戳我直达洛谷p5565）
该算法的步骤如下：
- 假设存在 A [ 0 ] A[0] A[0]和 A [ n + 1 ] A[n+1] A[n+1]，将它们的值设为无穷大。
- 从 1 1 1到 n n n，找到第一个 k k k使 A [ k − 1 ] < = A [ k + 1 ] A[k-1] <= A[k+1] A[k−1]<=A[k+1]，保存这个 k k k。
- 定义一个临时变量 t e m p temp temp，使 t e m p = A [ k − 1 ] + A [ k ] temp = A[k-1] + A[k] temp=A[k−1]+A[k]，同时 a n s = t e m p ans = temp ans=temp。
- 从 1 1 1到 k − 1 k-1 k−1，找到第一个 i i i 使 A [ i ] > t e m p A[i] > temp A[i]>temp，保存这个 i i i。
- 从表A 中同时删除 A [ k − 1 ] A [ k-1 ] A[k−1] 和 A [ k ] A[k] A[k]。
- 在 i i i 之后插入一个 t e m p temp temp。
- 重复步骤2到6共循环 n − 1 n-1 n−1次，最后 a n s ans ans即为答案。
这个算法可以帮助我们找到最小的合并次数，以使得石子合并的得分总和最小。
简单理解版：
因为合并 a , b , c a,b,c a,b,c有两种合并方式，价值分别为 a + 2 b + 2 c a+2b+2c a+2b+2c和 2 a + 2 b + c 2a+2b+c 2a+2b+c，因此我们只需要比较 a a a 和 c c c 即可，于是先合并 a < c a<c a<c的，完了之后如果还有剩就从右边开始合并 b c bc bc
合并 a b ab ab 的时候，合并之后插入从左边数第一个大于他的数的后面开始（原因本蒟蒻也不理解www）文章来源：https://www.toymoban.com/news/detail-623860.html
具体的实现可以用邻接表或者vector，以下给出vector的做法文章来源地址https://www.toymoban.com/news/detail-623860.html
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int INF=0x7f7f7f7f;
int a[N],n,tmp;
long long int ans=0;
vector<int> v;
void work(){
int kk=v.size()-2,q=-1,tmp;//
for(int k=0;k<v.size()-2;k++){//如果我们在A[0]到A[n-3]找不到A[k]<=A[k+2]，那么k的值应该为n-2
if(v[k]<=v[k+2]){
kk=k;break;
}
}
tmp=v[kk]+v[kk+1];
for(int i=kk-1;i>=0;i--){//从右往左找第一个
if(v[i]>tmp){
q=i;break;
}
}
v.erase(v.begin()+kk);
v.erase(v.begin()+kk);//删除元素
v.insert(v.begin()+q+1,tmp);//因为是在后面插入，所以要+1
ans+=tmp;//答案累加
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
v.push_back(a[i]);
}
for(int t=1;t<=n-1;t++){
work();
}
printf("%lld",ans);
return 0;
}
ps： 这玩意看着简单打起来好多坑
完结撒花~~~ （终于写完了）
附封面
到了这里，关于石子合并一章通（环形石子合并，四边形不等式，GarsiaWachs算法）（内附封面）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![动态规划——区间dp [石子合并]](https://imgs.yssmx.com/Uploads/2024/02/533080-1.png)
