UVA10559 方块消除 Blocks（区间dp）

一道区间dp好题，在GZY的ppt里，同时在洛谷题解里看见了Itst orz。

题目大意

有n个带有颜色的方块，没消除一段长度为 \(x\) 的连续的相同颜色的方块可以得到 \(x^2\) 的分数，用一种最优的顺序消除所有方块使得得分最多。

Solution

一开始用的常规操作，设 \(f_{i,j}\) 表示区间 \([i,j]\) 的最大得分，然后发现转移的时候很麻烦，此时瞄了一下题解，发现神奇的设状态方法：

\(f_{i,j,k}\) 表示区间 \([i,j]\) 且右边有 \(k\) 个和 \(j\) 颜色相同的方块，合并所有这些方块的最大得分。

考虑转移，有两种情况，一是把最后 \(k+1\) 个方块一起消掉，此时

\[f_{i,j,k}=f_{i,j-1,0}+(k+1)^2
\]

二是在区间 \([i,j-1]\) 之间选一个与 \(j\) 颜色相同的方块 \(p\) ，将 \([p+1,j-1]\) 消掉，使得 \(p\) 和 \(j\) 相邻，再消掉全部，此时

\[f_{i,j,k}=f_{p+1,j-1,0}+f_{i,p,k+1}
\]

最后，就是要注意转移时的顺序， \(i\) 应该从大到小枚举，因为是从右边转移到左边。

Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define _FILE(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)

using namespace std;

const int maxn = 200 + 10;

int n, a[maxn], f[maxn][maxn][maxn], num[maxn];

int main()

{

#ifndef ONLINE_JUDGE

	_FILE("a");

#endif

    int T, kase = 0;

    cin >> T;

    while (T--) {

        cin >> n;

        memset(f, 0, sizeof(f));

        memset(num, 0, sizeof(num));

        for (int i = 1; i <= n; ++i)

            scanf("%d", &a[i]);

        for (int i = 1; i <= n; ++i)

            for (int j = i + 1; j <= n; ++j)

                if (a[i] == a[j])

                    ++num[i];

        for (int i = n; i >= 0; --i) {

            for (int j = i; j <= n; ++j) {

                for (int k = i; k < j; ++k)

                    if (a[j] == a[k]) {

                        for (int p = 0; p <= num[j]; ++p)

                            f[i][j][p] = max(f[i][j][p], f[k + 1][j - 1][0] + f[i][k][p + 1]);

                    }

                for (int p = 0; p <= num[j]; ++p)

                    f[i][j][p] = max(f[i][j][p], f[i][j - 1][0] + (p + 1) * (p + 1));

            }

        }

        printf("Case %d: %d\n", ++kase, f[1][n][0]);

    }

	return 0;

}