石子归并 (区间DP)

题目链接51nod-1021

题目描述

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如: 1 2 3 4,有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出,第一种方法的代价最低,现在给出n堆石子的数量,计算最小合并代价。

输入
第1行:N(2 <= N <= 100)
第2 - N + 1:N堆石子的数量(1 <= A[i] <= 10000)
输出
输出最小合并代价
输入样例
4
1
2
3
4
输出样例
19

思路

在没学习DP前,我会把这题考虑成为一个贪心题;
要使合并代价最小,我们可以使权值较大的最后合并,减少权值较大的计算次数来减少最小合并代价;
即局部考虑最优,然后整体最优;这是贪心的思想,但是这个结论却是错误的;

举个例子解释一下,
4
6 5 5 6
我们第一步选择合并代价最小的,即合并5 和 5
新的石子堆 6 10 6 此时代价 = 10 。然后我们再次合并所需代价最小的;即合并6 10
新的石子堆 16 6 代价 = 10 + 16。 然后再次合并
新的石子堆 2 2 代价 = 10 + 16 + 22 = 48
按照贪心的思想, 我们使得局部最优得到的解时是 48 , 这个结果对不对呢?答案是错误的;比如
我们第一步合并6,5.得到 11 5 6 代价为 11
我们第二步合并5,6.得到 11 11 代价为 11 + 11
我们第三步合并11,11.得到 22 代价为 11 + 11 + 22 = 44;

显然局部最优并非整体最优,所以我们得用动态规划来求解;

我们可以定义状态dp[i][j]代表从i到j的合并所需的最小代价;
状态转移方程就是 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + val);
这里的val指的是当i->k已经合并为1堆,k+1->j合并为一堆;合并这两堆的代价;
在本题中就是i->j的一个区间和,我们可以用前缀和来维护一下就可以;

我们在最外层枚举选取合并长度,第二层枚举起点,第三层枚举分割点即可;

注意

算法复杂度为O(n^3);
计算最小代价初始化为INF;
计算最大代价初始化为-INF;

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MAX_N 110

int a[MAX_N], sum[MAX_N], dp[MAX_N][MAX_N];//a记录输入数据 sum为前缀和

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;
for(int i = 1; i <= n; i++)//计算最小代价 初始为INF
{
for(int j = i; j <= n; j++)
{
dp[i][j] = INF;
}
}
for(int i = 1; i <= n; i++)//录入数据并计算前缀和
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
dp[i][i] = 0;
}
for(int k = 1; k <= n; k++)//枚举选取长度
{
for(int i = 1; i + k - 1 <= n; i++)//枚举长度 i + k - 1即为终点 保证终点 <= n
{
int ends = i + k - 1;// ends为终点
for(int j = i; j < ends; j++)// 枚举分割点
{
dp[i][ends] = min(dp[i][ends], dp[i][j] + dp[j+1][ends] + sum[ends] - sum[i - 1]);
}
}
}
cout << dp[1][n] << endl;

return 0;
}
-------------本文结束,感谢您的阅读!-------------