更多提高课题目题解,欢迎访问我的提高课学习笔记+题解总结(更新中)
题目描述
现有 $n$ 堆呈环状放置的石子堆,给定每堆石子的数量 $w_i$
规定合并操作可将相邻的两堆石子合并为一堆新的石子,合并的费用是两个石子堆的数量之和
需求解两个方案:
- 将所有石子合并为1堆,且消耗费用最小的方案
- 将所有石子合并为1堆,且消耗费用最大的方案
并分别输出总费用的最大值与最小值
分析
本题要求每次只能合并相邻两堆的石子,且费用仅受被合并的两堆石子数量影响,是一个标准的区间DP
本题是由一道经典的区间DP模板题目石子合并拓展得来,与原题目的区别在于此题要求合并的石子堆呈环形放置,即第 $1$ 堆可以与当前的第 $n$ 堆直接进行合并
对于区间DP的状态表示,可知影响某一区间合并费用最优解的因素仅为该区间的各个子区间最优解,故状态集合需既能表示初始每堆石子数量,又能表示合并后石子堆消耗费用,考虑使用区间位置与大小表示区间状态,即通过区间左右端点下标代表状态阶段划分
故可使用 $f_{l,r}$ 代表合并从左端点 $l$ 到右端点 $r$ 的所有石子堆所需费用的最大/小值
易知区间大小 $len=r-l+1$ ,将区间大小从小到大按序遍历,即可在每次求解当前区间最优解前将其各个子区间最优解求得
故状态转移方程为
$$
f_{l,r}=max/min(f_{l,k} + f_{k+1,r} + sum_{l,r}) (l \leq k < r)
$$
其中 $sum_{l,r}$ 代表从石子堆 $l$ 到 $r$ 的数量之和,即当前本次合并所消耗的费用
此方法需枚举区间长度 $len$ ,左端点位置 $l$ ,与中间节点位置 $k$, $r$ 的位置可由 $len$ 与 $l$ 求得,时间复杂度为 $O(n^3)$
对于环形序列的处理,常见有以下两种方式:
- 将 $n$ 堆石子看做 $n$ 个点,每次合并操作看做在相邻两个点间建一条边,则经过 $n-1$ 次操作可将 $n$ 堆石子合并为 $1$ 堆石子,即构建了 $n-1$ 条边,可以通过枚举两点间不存在边的位置,将环还原成链,需要枚举 $n$ 次,时间复杂度为 $O(n^4)$
- 可以将序列延长至两倍,变成 $2n$ 个堆,设其中第 $i$ 堆与第 $i+n$ 堆为同样的石子堆,继续递推最长大小为 $n$ 的区间DP,最终即可求得从每个点开始的长度为 $n$ 的最优解,整体比较后可得到全局最大/最小值,时间复杂度为 $O(n^3)$
其中第2种方法效率较高,代码也更简洁,故第2种方法更常被使用
Code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=410;//因为将序列延长至两倍,故所需空间需乘2
int n,w[N],s[N],f[N][N],g[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[i+n]=w[i];//读入预处理
}
for(int i=1;i<=2*n;i++)
s[i]=s[i-1]+w[i];//预处理前缀和,便于进行区间和运算
memset(f,0xcf,sizeof f);//求最大值赋初值为最小值(由于此题不存在负数故本步可忽略)
memset(g,0x3f,sizeof g);//求最小值赋初值为最大值
for(int len=1;len<=n;len++)//枚举长度
for(int l=1;l+len-1<=2*n;l++)//枚举左端点(注意右端点判定条件)
{
int r=l+len-1;//根据区间大小与左端点计算右端点
if(l==r) f[l][r]=g[l][r]=0;//特判,如果只有一堆石子则合并费用为0
for(int k=l;k<r;k++)//枚举中间节点
{
f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
g[l][r]=min(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
}
}
int maxn=-0x3f3f3f3f,minn=0x3f3f3f3f;//比较,获得最终答案
for(int i=1;i<=n;i++)
{
maxn=max(maxn,f[i][i+n-1]);
minn=min(minn,g[i][i+n-1]);
}
printf("%d\n%d\n",minn,maxn);
return 0;
}