Uva 10559 消除方块

题意：

每次可以选择一个区间（连续相同的序列）消除，得分为 len*len；问最大得分。

分析：

很容易想到是区间DP，但是不像普通的区间DP一样切割方式~~~

如果定义 d[ i ][ j ] 区间，那么在里面切割，将有两个部分，而且中间的要连续相等，连续相等的区间可能还要枚举，加上 判断连续相等，可能会时间超，而且不是就算枚举了，剩下的还要合并，确实麻烦。

一种新的区间DP状态定义： d[i][j][k] 区间 i ~ j 后面继续加 k 个字符（与 j 相同）的最优解。

那么答案是： d[1][n][0]；

状态转移：首先一种情况是 d[i][j-1][0] + (k+1)^2；

然后是切割方式：如何切割呢？

如果： i 和 r 颜色相同，这里就有可能产生一种切割方式，首先是中间部分 d[i+1][r-1][0] ，然后是合并部分，d[l][i][k+1]；

新思维，巧妙解决合并的问题~~~

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

int n,v[maxn];

int d[maxn][maxn][maxn];

int dp(int l,int r,int k) {

    if(l>r) return ;

    int& ans = d[l][r][k];

    if(ans) return ans;

    ans = dp(l,r-,) + (k+)*(k+);

    for(int i=r-; i>=l; i--) {

        if(v[i]==v[r]) {

            ans = max(ans,dp(l,i,k+)+dp(i+,r-,));

        }

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    for(int z = ; z<=t; z++) {

        scanf("%d",&n);

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

        memset(d,,sizeof(d));

        printf("Case %d: %d\n",z,dp(,n,));

    }

    return ;

}