POJ 1390 Blocks（区间DP + 记忆化搜索）

题意：

一排带有颜色的砖块，每一个可以消除相同颜色的砖块，每一次可以到块数 k 的平方分数。问怎么消能使分数最大。

思路：

1. 此题是结合区间动态规划和记忆化搜索的好题，状态转移方程不太好想，以下思路还是根据黑书上面的解释来的;

2. dp[i, j, k] 表示区间 [i, j] 并且在区间后面还有长度为 k 的砖块和 j 的颜色一致;

3. 如果 j 就和后面的 k 个结合则有：dp[i, j-1, 0] + (len[j] + k) ^ 2;

4. 如果 j 和前面若干段结合，并且前面若干段最后一段是 p，则有：dp[i, p, len[j]+k] + dp[p+1, j-1, 0];

5. 列出了上述方程式，用线性的方法是无法胜任的，因为 k 无法确定。这时候采取记忆化搜索的办法，从后往前来，问题得到解决;

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 210;

int dp[MAXN][MAXN][MAXN];
int color[MAXN], len[MAXN], pre[MAXN], table[MAXN], block[MAXN];

int solvedp(int l, int r, int k) {
    if (l > r) 
        return 0;

    if (dp[l][r][k] != -1)
        return dp[l][r][k];
    
    if (l == r) {
        return dp[l][r][k] = (len[r]+k)*(len[r]+k);
    }
    int ans;
    ans = solvedp(l, r-1, 0) + (len[r]+k)*(len[r]+k);

    for (int i = pre[r]; i >= l; i = pre[i]) {
        if (color[i] == color[r]) {
            ans = max(ans, solvedp(l, i, len[r]+k) + solvedp(i+1, r-1, 0));
        }
    }
    return dp[l][r][k] = ans;
}

int main() {
    int cases, cc = 0;
    scanf("%d", &cases);
    while (cases--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &block[i]);
        block[n] = n + 1;
        int colcnt = 0, calc = 1;
        memset(table, -1, sizeof(table));
        for (int i = 0; i < n; i++) {
            if (block[i] == block[i+1])
                calc += 1;
            else {
                color[colcnt] = block[i];
                len[colcnt] = calc;
                pre[colcnt] = table[block[i]];
                table[block[i]] = colcnt;
                calc = 1;
                colcnt += 1;
            }
        }
        memset(dp, -1, sizeof(dp));
        int ans = solvedp(0, colcnt - 1, 0);
        printf("Case %d: %d\n", ++cc, ans);
    }
    return 0;
}