<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1068.环形石子合并
将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。
请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算:
选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。
选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。
输入格式
第一行包含整数 $n$,表示共有 $n$ 堆石子。
第二行包含 $n$ 个整数,分别表示每堆石子的数量。
输出格式
输出共两行:
第一行为合并得分总和最小值,
第二行为合并得分总和最大值。
数据范围
$1 \le n \le 200$
输入样例:
4
4 5 9 4
输出样例:
43
54
dp方程
容易分析出,这道题是区间 dp
问题
基本结构: $f[i][j]$ 表示 区间 $[i, j]$ 的答案
枚举中点 $k$;$f[i][j] = min/max (f[i][k] + f[k + 1][j] + x[i ~ j])$
注:$x[i ~ j]$ 表示区间 $[i, j]$ 的 $x$ 数组的区间和
因为区间和只有查询,没有修改,考虑前缀和来维护区间和
前缀和数组 $a$:$a[i] = a[i - 1] + x[i]$,$x[i ~ j] = a[j] - a[i - 1]$
所以得出:$f[i][j] = min/max (f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1])$
枚举顺序:
很明显,长的区间由短的区间合并而成
所以先枚举区间长度 $len$
接着枚举左端点 $l$( 右端点由左端点和区间长度去确定)
最后枚举分段点 $k$,计算 dp
方程
变量解释
$n$:石子个数
$x$ 数组:$x[i]$ 表示 第 $i$ 个位置的石子个数
$a$ 数组:$x$ 数组的前缀和,a[i] = a[i - 1] + x[i],可以 在 $O(1)$ 的时间内查询 $x$ 数组的区间和
$f$ 数组:$f[i][j]$ 表示 区间 $[i, j]$ 的答案
$Min$:最小石子合并的答案
$Max$:最大石子合并的答案
#include <bits/stdc++.h>
using namespace std;
const int N = 409, INF = 1e9;
//注意 N 要开两倍空间!具体原因见输入
int n, x[N], f[N][N], a[N];
int Min = INF, Max = -INF;
int main()
{
ios :: sync_with_stdio(false);//读入优化
cin.tie(0);//读入优化
cin >> n;
for(int i = 1;i <= n * 2;++ i)
{
if(i <= n) cin >> x[i], x[i + n] = x[i];
//小细节,因为是环形,所以 我们可以把链延长两倍,变成 2n 个点
//其中 i 和 i+n 是相同的两个点,然后直接套 区间 dp 模板
//只要最终计算时,len 只枚举到 n,根据状态的定义,最终可以得到所求的方案,时间复杂度为 O(n ^ 3)
a[i] = a[i - 1] + x[i];//前缀和
}
//首先,我们先计算何并的最小值
for(int len = 1;len < n;++ len)//枚举len
for(int i = 1, j;i <= 2 * n - len;++ i)//枚举左端点
{
j = i + len;//计算右端点
f[i][j] = INF;//初始化f[i][j]
for(int k = i;k < j;++ k)//枚举k
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);//直接计算
if(len == n - 1) Min = min(Min, f[i][j]);//计算答案
}
//接着,我们计算合并的最大值
for(int len = 1;len < n;++ len)//枚举len
for(int i = 1, j;i <= 2 * n - len;++ i)//枚举左端点
{
j = i + len;//计算右端点
f[i][j] = 0;//初始化f[i][j]
for(int k = i;k < j;++ k)
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);//直接计算
if(len == n - 1) Max = max(Max, f[i][j]);//计算答案
}
cout << Min << endl << Max << endl;//输出
return 0;
}
太强了 大佬棒啊