思路以及证明

记颜色序列为a，长度序列为len
第一步将所有颜色相同的木块合并，由于贪心的原则，一定不会单独消除某一个木块而不去消除连带的与之颜色相同的木块，之后得到了一个相邻木块颜色不同有权值的木块序列，之后考虑[l,r]区间，其中在r的右边有k个颜色与a[r]相同的木块，刚开始没有消去时这个k都是0，只有后续操作才可以使得k值增加；此时分析一般情况，对于某一个状态f[l][r][k]来说，这种样式的区间带来的收益是多少？
消去这个[l, r + k]区间获得的最大的收益是多少，对于消去这个区间的方法，它可以分为：
1.直接将[r, r + k]消去，之后再消去[l, r - 1]；
2.先保留[r, r + k]，而先消除[k,r-1]之后看看前面能不能剩出与r相同颜色的木块，之后最后消，
现在证明分出的这两个集合是互不相交而且得到的是所有的情况：可以枚举所有消除r的时间（因为贪心，后面的k个一定和r一起消，枚举r的消除时间就是枚举[r, r + k]的消除时间）消r的时间分为r与[l, r - 1]中其他r的颜色还有间隔的时刻或者没有间隔的时刻，分别对应到先消[r, r + k]与先消[k, r - 1]其中k - 1与r颜色相同，那么就已经证明出来了这两种集合划分是有效的。
现在考虑状态的转移：
第一种：f[l][r][k] 可以由 f[l][r - 1][0] + (len[r] + k)^2 ….其中len代表init贪心得到的权值
第二种：如果[l, r - 1]区间中含有一个i 有i与r的颜色相同，
f[l][r][k] = 所有的满足条件的i : f[i + 1][r - 1][0] + f[l][i][len[r] + k]

于是证明一波是否转移是满足拓扑序列的（只有满足拓扑序才可以做）
首先初始化为 f[u][u][z] = (v[u] + z) ^ 2 如果f[l][r]有l > r的话直接pass不算，即为-inf（初始化为-inf）
对于某一个合法状态f[l][r][u]，它不可能到达l > r的状态，最多就是l == r，
而每次区间都会缩小，而缩小区间里面的所有只都应该被计算，如果没有被计算，也就是这种状态不存在，返回error也就是代价无穷大，直接记忆化搜索可以免去一些对不可能情况的计算，好一些。

由于初始化极其墨迹，并且循环总会计算一些没意义的东西（不可能成立的情况），直接采用记忆化搜索代码会短，但是需要多次的栈迭代（缺点）

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;
int f[N][N][N];
int len[N], a[N];
int arr[N];
int n;

int init()
{
    int j = 0;
    for(int i = 0 ; i <= n ; i ++)
    {
        if(i == 0)
        {
            len[j] = 1;
            a[j] = arr[i];
        }else if(arr[i] == arr[i - 1]){
            len[j] ++;
        }else{
            j ++;
            len[j] = 1;
            a[j] = arr[i];
        }
    }
    return j;
}

int dfs(int l, int r, int k)
{
    if(l > r) return f[l][r][k] = -100000; //不可能成立的情况
    if(l == r) return f[l][r][k] = (len[r] + k) * (len[r] + k); //相当于循环写的初始化
    if(~f[l][r][k]) return f[l][r][k];
    int res = dfs(l, r - 1, 0) + (len[r] + k) * (len[r] + k);
    for(int i = l ; i < r ; i ++)
    {
        if(a[i] == a[r]) res = max(res, dfs(i + 1, r - 1, 0) + dfs(l, i, len[r] + k));
    }
    return f[l][r][k] = res;
}

int main()
{
    int T;
    cin >> T;
    for(int t = 1 ; t <= T ; t ++){
        cin >> n;
        for(int i = 0 ; i < n ; i ++) cin >> arr[i];
        n = init();
        memset(f, -1, sizeof f);
        cout << "Case " << t << ": " << dfs(0, n - 1, 0) << endl;
    }
    return 0;
}