UVA10559 Blocks(方块消除)

Link

题意很明确了，像这种消除一小块同色的东西获得一些分数，让你使这个分数最大的题目多半可以考虑区间DP

不妨先试：设 f[l][r] 表示从 l 消到 r 可获得的最大分数。枚举一个中间转移的断点 k

这样设是最直接的状态。最大的问题是这么设中间的颜色非常不好处理，仍然需要再从l 遍历到 k 和从 k + 1 遍历到 r，看颜色是否相同，可以消除。那么这么做的复杂度是 O(n^4)

考虑另一种状态，设 f[l][r][k] 表示从 l 消到 r 并且在 r 后还有 k 个与 r 位置上的方块同色的方块

考虑 k =0 的特殊情况，那么它肯定由右边界的上一个位置 r-1 转移过来，则 f[l][r][0] = max(f[l][r][0],f[l][r - 1][0] + 1)

因为 k=0 也可以写成：f[l][r][0] = max(f[l][r][0],f[l][r - 1][0] + (k+1)^2)

推广到全部情况，设 l \leq p ，则有：f[l][r][k] = max(f[l][r][k], f[l][p][k+1]+f[p+1][r-1][0])

实现的时候借鉴了神tst的预处理每一个位置上颜色相同的个数的方法，具体实现见代码。

类似的比较巧妙的区间DP推荐：P3147 [USACO16OPEN]262144

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 200 + 5;

int T, n;
int a[SIZE], sum[SIZE], f[SIZE][SIZE][SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void init()
{
    memset(f, 0, sizeof(f));
    memset(sum, 0, sizeof(sum));
}

int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    T = read();
    int ind = 0;
    while (T--) {
        ind++;
        n = read();
        for (int i = 1; i <= n; i++) a[i] = read();
        for (int i = n - 1; i >= 1; i--)
            for (int j = i + 1; j <= n; j++) {
                if (a[i] == a[j]) sum[i]++;
            }
        for (int i = n; i >= 1; 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 <= sum[k]; p++)
                            f[i][j][p] = std::max(f[i][j][p], f[k + 1][j - 1][0] + f[i][k][p + 1]);
                    }
                }
                for (int k = 0; k <= sum[j]; k++) {
                    f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][0] + (k + 1) * (k + 1));
                }
            }
        std::cout << "Case " << ind << ": " << f[1][n][0] << endl;
        init();
    }
    return 0;
}