我要评论
一、石子合并
1、定义
设有
n
n
n堆石子排成一排，其编号为
1
1
1，
2
2
2，
3
3
3，…，
n
n
n。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这
n
n
n堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如：
例如有
4
4
4堆石子分别为
1
1
1
3
3
3
5
5
5
2
2
2， 我们可以先合并
1
1
1、
2
2
2堆，代价为
4
4
4，得到
4
4
4
5
5
5
2
2
2， 又合并
1
1
1、
2
2
2堆，代价为
9
9
9，得到
9
9
9
2
2
2，再合并得到
11
11
11，总代价为
4
+
9
+
11
=
24
4+9+11=24
4+9+11=24；
如果第二步是先合并 2 2 2、 3 3 3堆，则代价为 7 7 7，得到 4 4 4 7 7 7，最后一次合并代价为 11 11 11，总代价为 4 + 7 + 11 = 22 4+7+11=22 4+7+11=22
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
2、闫氏dp分析法
3、模拟过程
1、状态：
f
[
l
,
r
]
f[l,r]
f[l,r]表示把从
l
l
l到
r
r
r合并成一堆的最小代价。
利用前缀和求区间和
- 先把区间 [ l , r ] [l,r] [l,r]切分为两部分 [ l , k ] [l,k] [l,k]和 [ k + 1 , r ] [k+1,r] [k+1,r]， k k k是切分点；
- 再把两部分 [ l , k ] [l,k] [l,k]和 [ k + 1 , r ] [k+1,r] [k+1,r]合并在一起。
状态转移方程如下：
f
[
l
,
k
]
+
f
[
k
+
1
,
r
]
+
s
[
r
]
−
s
[
l
−
1
]
⇒
f
[
l
,
r
]
f[l,k]+f[k+1,r]+s[r]-s[l-1]\rarr f[l,r]
f[l,k]+f[k+1,r]+s[r]−s[l−1]⇒f[l,r]
2、计算：
f
[
l
,
r
]
=
m
i
n
(
f
[
l
,
r
]
,
f
[
l
,
k
]
+
f
[
k
+
1
,
r
]
+
s
[
r
]
−
s
[
l
−
1
]
)
f[l,r]=min(f[l,r],f[l,k]+f[k+1,r]+s[r]-s[l-1])
f[l,r]=min(f[l,r],f[l,k]+f[k+1,r]+s[r]−s[l−1])
3、初值：
f
[
i
,
j
]
=
0
f[i,j]=0
f[i,j]=0（合并每个石子的代价为
0
0
0），其余为正无穷
4、目标：
f
[
1
,
n
]
f[1,n]
f[1,n]
4、代码示例
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int n = 310;
int n;
int dp[n][n], s[n];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {//区间的移动
int r = l + len - 1;
dp[l][r] = 1e9;
for (int k = l; k < r; k++) {
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
}
}
}
printf("%d", dp[1][n]);
return 0;
}
发表评论