UVa10559 Blocks

发表于 | 分类于 |
字数统计: 485 字

题目大意：有$n$个带有颜色的方块，消除一段长度为$x$的连续的相同颜色的方块可以得到$x^2$的分数，求一种最优的消除顺序消除所有方块使得得分最多。

题解

设 $f(i, j, k)$ 为当前区间为 $[i, j]$，且区间中消除到有 $k$ 个和 $i$ 处颜色相同的方块时，可以得到的最大分数。显然，答案为 $f(1, n, 0)$。
当 $k\neq 0$ 时，要考虑从 $k-1$ 转移过来。此时考虑从 $[i, j]$ 中遍历 $l$，当第 $l$ 个方块颜色和第 $i$ 个相同时，将从 $l$ 左或者从 $l$ 右开始的一部分作为从 $k-1$ 转移过来的部分，另一部分消去。因为消去的顺序不影响结果，此处将右边一半消去。从而有：

当 $k=0$ 时，考虑将积累下来的方块消去，就有：

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[205] = {0};
int f[205][205][205] = {0};
int main(){
    int T;
    scanf("%d", &T);
    for(int TT = 1; TT <= T; ++TT){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        memset(f, -1, sizeof(f));

        for(int i = 1; i <= n; ++i)
            f[i][i][1] = 0, f[i][i][0] = 1;
        for(int i = 0; i <= n; ++i)
            for(int j = i - 1; j >= 0; --j)
                f[i][j][0] = 0;
        f[n + 1][n][0] = 0;

        for(int i = 1; i < n; ++i){
            for(int j = 1; j + i <= n; ++j){
                for(int k = 1; k <= i + 1; ++k){
                    for(int l = j; l <= j + i; ++l){
                        if(a[j] != a[l]) continue;
                        if(f[j][l - 1][k - 1] >= 0)
                            f[j][j + i][k] = max(f[j][j + i][k], f[j][l - 1][k - 1] + f[l + 1][j + i][0]);
                    }
                }
                for(int k = 1; k <= i + 1; ++k){
                    if(f[j][j + i][k] >= 0)
                        f[j][j + i][0] = max(f[j][j + i][0], f[j][j + i][k] + k * k);
                }
            }
        }
        printf("Case %d: %d\n", TT, f[1][n][0]);
    }
    return 0;
}