2.2 消除方块

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

YellowStar 有 \(n\) 个方块排成一列，标号为 1 到 \(n\)，每个方块有两个属性 \(a\)、 \(b\)。现在他要把这些方块一个接一个的消除掉，每次消除一个方块，Yellowstar 需要花费当前方块的 \(a\) 数值，加上当前方块左边和右边的第一个方块的 \(b\) 数值的总和的代价（如果左边或右边没有方块，则没有代价）。一个方块被消除后即消失，其余方块顺序保持不变。

现在 Yellowstar 可以决定方块的消除顺序，他想花费最小的代价消除掉所有方块，请你帮助他。

数据输入

输入的第一行为数字 \(n\ (2\leq n\leq 200)\)，表示给定方块的个数；第二行包含 \(n\) 个整数，表示方块的第一个属性 \(a_1, a_2, \cdots, a_n\ (0\leq a_i\leq 10^5)\)；第三行包含 \(n\) 个整数，表示方块的第二个属性 \(b_1, b_2, \cdots, b_n\ (0\leq b_i\leq 10^5)\)。

数据输出

输出一个整数，表示最小代价。

输入示例 输出示例
3
3 5 7
8 2 0		 17
5
0 0 0 0 0
10 50 100 50 10		 190

数据范围

\(80\%\)的得分点，\(n \leq 10\)；\(20\%\)的得分点，\(n \leq 200\)。

提示

样例 1 最优顺序为，消除 1 方块，消除 2 方块、 消除 3 方块。消除 1 方块 \(3+2=5\)，消除 2 方块 \(5+0=5\)，消除 3 方块 \(7+0=7\)。总代价为：\(5+5+7=17\)。

样例 2 最优顺序为，消除 3 方块，消除 2 方块、 消除 4 方块、 消除 1 方块、 消除 5方块。消除 3 方块 \(50+50=100\)，消除 2 方块 \(50+10=60\)，消除 4 方块 \(10+10=20\)，消除 1 方块 10，消除 5 方块 0。

总代价为：\(100+60+20+10+0=190\)。

源代码

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
#include <stdio.h>
#define maxn 205
inline int min(const int a, const int b){ return a < b ? a : b; }
int dp[maxn][maxn];
int b[maxn];

int solve(int n){
    for (int i = n; i > 0; --i) {
        for (int j = i; j <= n; ++j) {
            if (j == i) { dp[i][j] = b[j - 1] + b[j + 1]; continue;}
            for (int k = i; k <= j; ++k) {
                if (k == i) {
                    dp[i][j] = dp[k + 1][j] + b[i - 1] + b[j + 1];
                }
                else if (k == j) {
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + b[i - 1] + b[j + 1]);
                }
                else {
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + b[i - 1] + b[j + 1]);
                }
            }
        }
    }
    return dp[1][n];
}

//区间dp问题
int main(){
    int i, n, suma = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i){
        scanf("%d", &b[1]);//借用一下
        suma += b[1];
    }
    for (i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    b[0] = b[n + 1] = 0;//增加两个空白方块方便处理
    printf("%d\n", suma + solve(n));
    return 0;
}

设计思路与复杂度分析

首先，无论以什么顺序处理，每一个\(a\)都只会被累加一次，所以\(a\)可以不参与算法过程而直接将\(\sum _{i=1}^{n}{a_i}\)加到算法结果中即可。

对于\(b\)的处理考虑分治算法。假设最后一个消除的方块为\(k\)时，有\([l,k-1]\)和\([k+1,r]\)两个区间的所有方块都已经消除，且消除这两个区间的代价已知。则只需将左右区间以及消除\(k\) 的代价加起来即可得到消除整个区间\([l,r]\)的代价。但是，并没有足够的条件确定\(k\)的具体值，所有需要遍历\(k\in [l,r]\)。以\(k\)为最后一个被消除的作为出发点而不是第一个的原因在于，\(k\)作为最后一个的时候其左右子区间的区间端点是明确的，而以\(k\)作为第一个的时候其左右子区间的区间端点不明确。

但是本题仅仅考虑分治还不够，复杂度过高。仔细推敲上面的分治算法会发现，算法在递归的时候会重复计算许多相同子区间的代价。这满足重叠子问题的性质，所以可以使用动态规划算法加速分治过程。算法时间复杂度为：\(O(n^3)\)。

0%