该题乍一看和矩阵链乘非常类似，但是有一个不同之处就是该题能够拼接 。

  为了达到这个目的。我们不得不拓展维度d[i][j][k]。用一个k表示最右边拼接了k个和a[j]同样颜色的方块。

问题的关键在于拼接，当右边存在一个q < p 且 a[q] == q[j] && a[q] != a[q+1] 时，能够拼接。要注意，全部满足这个条件的q都应该递归求解，由于哪一部分拼接起来更好，是不一定的 。

细节见代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 205;

int t,n,d[maxn][maxn][maxn],a[maxn],Case = 0;

int dp(int i,int j,int k) {

    int& ans = d[i][j][k];

    if(ans >= 0) return ans;

    ans = 0;

    int q = j+1,p = j,u;

    for(u=j;u>=i;u--) {  //求解p

        if(a[u]!=a[j]) break;

        else p = u;

    }

    if(p == i) return ans = ((j-p+1+k)*(j-p+1+k));//递归边界

    for(q=i;q<p;q++) { //求解q

        if(a[q] == a[j] && a[q+1] != a[j])

            ans = max(ans,dp(q+1,p-1,0) + dp(i,q,j-p+1+k) );//决策2

    }

    ans = max(ans,dp(i,p-1,0) + (j-p+1+k)*(j-p+1+k));//决策1

    return ans;

}

int main() {

    scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

        memset(d,-1,sizeof(d));

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

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

    }

    return 0;

}