参考 https://www.cnblogs.com/Tieechal/p/11637638.html

┭┮﹏┭┮

$f(l, r, k)$ 表示 消除 ($l$ ~ $r$ 和 拼接在 $r$ 之后连续 $k$ 个与 $r$ 颜色相同木块)的最大值

记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, cnt, test;
int col[N], len[N];
int f[N][N][N];

int dp(int l, int r, int k)
{
    if (l > r) return 0;
    if (l == r) return f[l][r][k] = (len[r] + k) * (len[r] + k);
    if (~f[l][r][k]) return f[l][r][k];

    f[l][r][k] = dp(l, r - 1, 0) + (len[r] + k) * (len[r] + k);

    for (int i = l; i < r; i ++ )
        if (col[i] == col[r])
            f[l][r][k] = max(f[l][r][k], dp(l, i, len[r] + k) + dp(i + 1, r - 1, 0));

    return f[l][r][k];
}

void solve()
{
    cnt = 0; 
    memset(f, -1, sizeof f);

    scanf("%d", &n);

    int last = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if (x != last) col[ ++ cnt] = x, len[cnt] = 1;
        else len[cnt] ++ ;

        last = x;
    }

    printf("Case %d: %d\n", ++ test, dp(1, cnt, 0));

}

int main()
{
    int T; scanf("%d", &T);
    while (T -- ) solve();

    return 0;
}

循环转移会有太多用不到的地方，K 值很多不会取到的， $n ^ {4}$ 超时

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210;

int n, test;
int col[N], sz[N];
int f[N][N][N];

void solve()
{
    memset(f, 0, sizeof f);
    scanf("%d", &n);
    int cnt = 0, last = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if (x != last) col[ ++ cnt] = x, sz[cnt] = 1;
        else sz[cnt] ++ ;
        last = x;
    }

    n = cnt;

    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            for (int k = 0; k < N; k ++ )
                if (l == r) f[l][r][k] = (sz[r] + k) * (sz[r] + k);
                else 
                {
                    f[l][r][k] = f[l][r - 1][0] + (sz[r] + k) * (sz[r] + k);
                    for (int i = l; i < r; i ++ )
                        if (col[i] == col[r])
                            f[l][r][k] = max(f[l][r][k], f[l][i][sz[r] + k] + f[i + 1][r - 1][0]);
                }
        }

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

int main()
{
    int T; scanf("%d", &T);

    while (T -- ) solve();

    return 0;
}

348