Description

题意：有一排数量为N的方块，每次可以把连续的相同颜色的区间消除，得到分数为区间长度的平方，然后左右两边连在一起，问最大分数为多少。

\(1\leq N\leq200\)

Solution

区间DP，对于一个连续的同色区间，可以直接消掉，或者从左边或者右边搞到和它同色的区间和在一起再一起消掉。

读入序列时预处理一下，将各个连续同色区间处理为一个点，记录它的颜色和长度，便于处理

然后就是区间DP啦，虽然要表示左边和右边，但是左边状态也可以表示为左边序列的右边，就只要开3维就行了

那么\(dp[i][j][k]\)表示区间\(i\)到区间\(j\)且在区间\(j\)右边添加\(k\)个格子的最大分数

1. 直接消除，即左边不考虑，为\(dp[i][j-1][0]+(len[j]+k)^2\)
2. 考虑左边，在\(j\)右边枚举\(p\),且\(color[j]==color[p]\),则为\(max\{dp[i][p][k+len[j]]+dp[p+1][j-1][0]\}\)

Code

#include 
    
     #include 
     
      #include 
      
       #define sq(a) ((a)*(a))#define N 210using namespace std;int T,col[N],dp[N][N][N],n,len[N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int DP(int l,int r,int k){    int &tmp=dp[l][r][k];    if(tmp>-1) return tmp;        tmp=DP(l,r-1,0)+sq(len[r]+k);    for(int p=l;p