Qjbtiger's Home
0%

夏令营7.17总结

Posted on Edited on In Views: Valine:

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

线段性动态规划（石子归并）：

【题目】地上有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.