0%

夏令营7.17总结

今天早上,我们不仅对昨天的最长公共子序列,有一些扩展,而且,还讲了线段性动态规划(石子归并)。

线段性动态规划(石子归并):

【题目】地上有N堆石子,每堆石子都有重量G[i]。现在,你可以将任意相邻的两堆石子i,j,合并成一堆,那么所花费的代价是G[i]+G[j],如此类推,知道只剩下一堆。问,代价最小是多少。

【输入】

【输出】

61

【理解题意】其实,题目意思就是,一串数字,每相邻的两个数可以相加,变成一个新的数,而结果要加上,这两个数之和。如图,这是一种分法。那么, 11+6+15+18+24=74。

他不见了。

下图也是一种分法(答案),代价为7+6+13+11+24=61。

他不见了。

【贪心(错误)】有人说,这题可以用贪心做,只要不断的把,相邻的,和最小的两个数合并,不就行了吗?

是吗?举出反例是最好的反驳。加入数据为[6,5,5,6],若按贪心做,则为[6,5,5,6],[6,10,6],[16,6],[22],代价为48,而正解为[6,5,5,6][11,5,6][11,11][22],代价为44。因此,贪心是不可行的。

【子问题】如果这一题用搜索,我们应该怎么做呢?当然是找子问题。我们知道,无论如何,合并成最后一堆的重量,一定是石子重量之和。如同样例,最后一堆,必定为24。那么,我们用反向思维来看,最后一堆终究是两堆石子合并成的,那么我们枚举它们最后一堆的合并位置,分成左右两堆的子问题,不就行了吗?

如图, [3,4,6,5,4,2]就可以分成[3,4,6,5]和[4,2]两个子问题,[3,4,6,5]的代价加上[4,2]的代价加上22,就是一种可能。再加上记忆化搜索,就可以实现了。

他不见了。

【动态规划】搜索虽然可行,但是也有弊端,就是容易爆栈,而且不容易表示,分了又分,难以表示。但是,子问题同样适用于动态规划,可以用动态规划解决。但是,难点又来了,怎么分阶段呢?

这是一个新知识点:以长度分阶段。我们可以用数组F[i][j]表示以i为起点,以j为终点,石子合并的最小代价。

当长度为1的时候,就是所有的石子都不用合并,所以,每一颗石子的代价为0,即F[i][j]=0(i=j)。

当长度为2的时候,[3,4]只有一个合并点,就是[3][4]之间,那么,[3,4]合并起来的代价就是,合并[3]的代价加上,合并[4]的代价,加上[3,4]的总重,即F[1][2]=F[1,1]+F[2][2]+G[i]+G[j];依此类推。

当长度为3的时候,如[3,4,5],有两个合并点,那么我们可以枚举合并点,一种可能是[3][4,5]那么代价为F[1][3]=F[1,1]+F[2,3]+G[1]+G[2]+G[3],还有一种可能,就是[3,4][5],代价为F[1][3]=F[1,2]+F[3,3]+G[1]+G[2]+G[3]。因此,我们要取所有可能的最小代价,那么结果才会最优。

注意到上面的下划线部分,这些都是相同的,因此,我们可以用预处理地方法,把第i到第j堆的重量算出来,以便于计算。

……

7 10 11 9 6

20 25 24 17

36 38 34

51 48

61

做完长度为N的DP时,就结束了。输出,F[i][j]。

因为这是从第i个到第j个的最优质,从数轴上看,这就像一条线段,因此,这种动态规划,叫做线段性动态规划;

程序如下:

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
#include <fstream>
using namespace std;

ifstream fin("storm_merge.in");
ofstream fout("storm_merge.out");

#define maxn 80

int storm[maxn],n;
int cnt[maxn][maxn],F[maxn][maxn];

int main() {
fin >> n;
for (int i=0; i!=n; ++i)
fin >> storm[i];//读入

for (int i=0; i!=n; ++i)
for (int j=i; j!=n; ++j)
cnt[i][j]=cnt[i][j-1]+storm[j];//预处理

for (int p=0; p<=maxn; ++p)
for (int q=0; q<=maxn; ++q)
F[p][q]=100000000;//要求最小,所以所有的到家初始化为正无穷

for (int p=0; p!=n; ++p)
F[p][p]=0;//当i=j时,F[i][j]为0

for (int len=2; len<=n; ++len)//以长度划分阶段
for (int l=0; l<=n-len; ++l) {//枚举左端点
int r=l+len-1;//从而确定右端点

for (int mid=l; mid!=r; ++mid) {//枚举合并点
F[l][r]=min(F[l][r],F[l][mid]+F[mid+1][r]+cnt[l][r]);//DP状态转移方程
}
}

fout << F[0][n-1] << endl;//输出
return 0;
}

【感受】第一次接触线段性动态规划,这是一个难点,也是重点。但是,我一定能够熟练掌握的。

Thank you so much.