[UVA10559]Blocks

DP

题面

有$n$个带有颜色的方块，消除一段长度为$x$的连续的相同颜色的方块可以得到$x^2$的分数。
用一种最优的顺序消除所有方块使得得分最多。

• $n\leq200$

解析

状态相当神仙。。。转移也很神仙。。。
设$f[l][r][k]$表示处理区间$[l,r]$，后面还有$k$个和右端点颜色相同的方块。
然后有三种转移：

• 消掉右端点那一段，即$f[l][r][k]=f[l][r-1][0]+(k+1)^2$
• 选一个区间内与右端点颜色相同的点$p$，消掉$[p+1,r-1]$使$p,r$相邻，即$f[l][r][k]=f[l][p][k+1]+f[p+1][r-1][0]$。
• 拆分问题，即$f[l][r][k]=f[l][i][0]+f[i+1][r][k]$

据此记搜即可。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int T,n,f[205][205][205],a[205];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int pf(re int x){return x*x;}
il int dfs(re int l,re int r,re int k)
{
  if(~f[l][r][k]) return f[l][r][k];
  if(l>r) return 0;
  re int &x=f[l][r][k],p;
  x=dfs(l,r-1,0)+pf(k+1);
  fp(i,l,r-1) p=dfs(l,i,0)+dfs(i+1,r,k),x=(x>p)?x:p;
  fp(i,l,r-1)
    if(a[i]==a[r]) p=dfs(l,i,k+1)+dfs(i+1,r-1,0),x=(x>p)?x:p;
  return x;
}
int main()
{
  re int T=gi();
  fp(o,1,T)
    {
      n=gi();
      fp(i,1,n) a[i]=gi();
      memset(f,-1,sizeof(f));
      printf("Case %d: %d\n",o,dfs(1,n,0));
    }
  return 0;
}