题目描述
还记得经典题石子合并吗？现在小
Y
Y
Y 将题目加强啦！
在一个圆形操场的四周摆放着
n
n
n 堆石子，现要将石子有次序地合并成一堆。规定每次只能选取相邻的三堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，读入石子堆数
n
n
n 及每堆的石子数。选择一种合并石子的方案，使得做
(
n
−
1
)
/
2
(n − 1) / 2
(n−1)/2 次合并，得分的总和最小。
输入格式
第
1
1
1 行
1
1
1 个数，表示石子堆数。
第
2
2
2 行是顺序排列的各堆石子数（
≤
1000
\le 1000
≤1000），每两个数之间用空格分隔。
输出格式
输出合并的最小得分。
样例
样例输入1：
5
1 2 3 4 5
样例输出1：
21
样例1解释：
先合并
(
1
,
2
,
3
)
(1, 2, 3)
(1,2,3)，再合并
(
6
,
4
,
5
)
(6, 4, 5)
(6,4,5)。
数据范围
对于
20
%
20\%
20% 的数据，
n
=
5
n = 5
n=5。
对于
60
%
60\%
60% 的数据，
n
≤
80
n \le 80
n≤80。
对于
100
%
100\%
100% 的数据，
3
≤
n
≤
400
3 \le n \le 400
3≤n≤400。
题解
由于是圆形的，所以需要破环为链，这里我直接复制一份到后面即可。
对于 20 % 20\% 20% 的数据，先合并三堆后，只剩下三堆，直接枚举即可。
对于
60
%
60\%
60% 的数据，和合并石子差不多，依然是 区间dp。
d
p
i
,
j
=
m
i
n
{
d
p
i
,
k
1
+
d
p
k
1
+
1
,
k
2
+
d
p
k
2
+
1
,
j
+
s
u
m
j
−
s
u
m
i
−
1
}
dp_{i, j} = min\{dp_{i, k1} + dp_{k1 + 1, k2} + dp_{k2 + 1, j} + sum_j - sum_{i - 1}\}
dpi,j=min{dpi,k1+dpk1+1,k2+dpk2+1,j+sumj−sumi−1}。
枚举长度和左端点，计算右端点，枚举两个断点进行转移。
复杂度为
Θ
(
n
4
)
\Theta(n^4)
Θ(n4)。
如果这道题你写的
60
60
60 分代码是
20
20
20 分，可以试一下以下数据：
输入
7
1 3 4 2 5 1 5
输出
37
解释
先合并
(
1
,
5
,
1
)
(1, 5, 1)
(1,5,1)，再合并
(
3
,
4
,
2
)
(3, 4, 2)
(3,4,2)，最后合并
(
9
,
5
,
7
)
(9, 5, 7)
(9,5,7)。
int f[810][810];//dp
int sum[810];//前缀和
int main(){
输入
//破环为链
for(int i = 1; i <= n; ++ i){
a[i + n] = a[i];
}
//初始化
for(int i = 1; i <= 2 * n; ++ i){
f[i][i] = 0;
f[i][i + 1] = 0x3f3f3f3f;
f[i][i + 2] = a[i] + a[i + 1] + a[i + 2];
sum[i] = sum[i - 1] + a[i];
}
//转移
for(int l = 4; l <= n; ++ l){//长度
for(int i = 1; i <= 2 * n - l; ++ i){//左端点
int j = i + l - 1;//[i, j]
//[i, k1] + [k1 + 1, k2] + [k2 + 1, j]
f[i][j] = 0x3f3f3f3f;
//枚举断点
for(int k1 = i; k1 <= j; ++ k1){
for(int k2 = k1; k2 <= j; ++ k2){
f[i][j] = min((long long)f[i][k1] + f[k1 + 1][k2] + f[k2 + 1][j] + sum[j] - sum[i - 1], (long long)f[i][j]);
}
}
}
}
//统计答案
int ans = 0x3f3f3f3f;
for(int i = 1; i <= n; ++ i){
ans = min(ans, f[i][n + i - 1]);
}
}
对于 100 % 100\% 100% 的数据，时间复杂度肯定超了。
这时我们考虑原版合并石子问题，只需要枚举一个断点，而当前枚举了两个断点。
将两个断点想成先断一处，再断一处。
先断就相当于原版合并石子问题，再断一处就从先断处理出的值和另外一边的值转移即可。
复杂度为
Θ
(
n
3
)
\Theta(n^3)
Θ(n3)。
int main(){
输入，破环为链
//预处理
for(int i = 1; i <= 2 * n; ++ i){
f[i][i] = 0;
f[i][i + 1] = 1e16;
sum[i] = sum[i - 1] + a[i];
}
for(int l = 3; l <= n; ++ l){
for(int i = 1; i <= 2 * n - l; ++ i){
int j = i + l - 1;
f2[i][j] = f[i][j] = 1e16;
//预处理先断
for(int k1 = i; k1 < j; ++ k1){
f2[i][j] = min((long long)f[i][k1] + f[k1 + 1][j], (long long)f2[i][j]);
}
//后断
for(int k2 = i; k2 < j; ++ k2){
f[i][j] = min((long long)f2[i][k2] + f[k2 + 1][j] + sum[j] - sum[i - 1], (long long)f[i][j]);
}
}
}
统计答案
}