Blocks

鬼畜dp，状态设计十分反人类。

这道题最显然的做法肯定是：dp[i][j]表示消去i,j的最大价值。但是这道题有一个问题：左右端点两边的连续的块可能会对她产生影响。这就十分难受。有一个常见的套路就是加维。
令：dp[i][j][k]代表：消除i - >j区间，且j连接着K个与j颜色相同的块的最大价值。为什么不需要记录左端点的？因为左端点的可以由之前的右端点代替。
转移：
1、$$dp[i][j][k]= max(dp[i][j][k],dp[i][j-1][0]+(k+1)^2)$$
2、$$dp[i][j][k]=max(dp[i][p][k+1],dp[p+1][j-1][0]);(col[p])==col[j]$$

为什么要这么转移？
第一个：我们可以直接消掉右端点以及右端点连接的方块。
第二个：我们可以在之前找一个断点（要求颜色相等）将右端点到这个断点之间的块都消掉，然后两者合为一起。
首先，为什么要选颜色一样的？这很显然，因为长度越长，平方之后越大。
其次，这样转移为什么是对的呢？这个我一开始根本没法理解，但是写了写记忆化搜索就理解了：
我们来观察记忆化的实现：

    if(i>j)return 0;
    if(dp[i][j][k])return dp[i][j][k];
    dp[i][j][k]=max(dp[i][j][k],dfs(i,j-1,0)+(k+1)*(k+1));
    for(int p=bef[j];p>=i;p=bef[p]) dp[i][j][k]=max(dp[i][j][k],dfs(i,p,k+1)+dfs(p+1,j-1,0));
    return dp[i][j][k];

我们一开始是从最大的区间开始，然后进行两种转移：一开始第一种肯定是没法转移的，对于第二种：中间我们需要求出消掉一段区间的代价，这又成为了一个子问题了，之后两段区间合并，前边那个区间的最优解也成为了一个子问题，这么不断递归下去就行了。如果不明白，可以画画图。

完整代码：

#include<bits/stdc++.h>
#define int long long
#define ldb double
#define maxn 250
using namespace std;
int n,col[maxn],bef[maxn],las[maxn],dp[maxn][maxn][maxn];
inline int dfs(int i,int j,int k)
{
    if(i>j)return 0;
    if(dp[i][j][k])return dp[i][j][k];
    dp[i][j][k]=max(dp[i][j][k],dfs(i,j-1,0)+(k+1)*(k+1));
    for(int p=bef[j];p>=i;p=bef[p]) dp[i][j][k]=max(dp[i][j][k],dfs(i,p,k+1)+dfs(p+1,j-1,0));
    return dp[i][j][k];
}
signed main()
{
    int t;
    cin>>t;
    for(int gg=1;gg<=t;++gg)
    {
        cin>>n;
        memset(las,0,sizeof(las));
        memset(dp,0,sizeof(dp));
        memset(bef,0,sizeof(bef));
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&col[i]);
            bef[i]=las[col[i]];
            las[col[i]]=i;
        }
        printf("Case %lld: %lld
",gg,dfs(1,n,0));
    }
    return 0;
}

收获：

我认为比较显然的dp转移可以用递推的写法（简洁）但是有时候一些比较奇怪的dp可以尝试用记忆化，两者各有利弊。
并且：有时候感觉状态的维度不足以描述一个状态时，要勇敢地升高维度。