UVA 10599 Blocks 解题报告 (动态规划)

UVA-10599 Blocks

题意

有 (n) 个有颜色的方块 (( n le 200)).

每次可以把任意 (x) 个连续的同色方块消除, 得到的收益为 (x^2).

求把所有方块消去后的最大收益.

思路

一道非常巧妙的 dp 状态设计题.

这题的暴力除了搜索以外似乎没有什么想法,

因为有些方块在初始序列中并不在一起, 但它们又可以在同一时刻消去, 用一般的区间 dp 的话肯定不行.

那归根到底, 不好处理的原因就是我们很难确定要把哪几个方块一起消去, 那我们不妨把它设计进 dp 状态里.

我们就以一个区间右端点的方块颜色为准, 钦定它右边的 (k) 方块和它一起消去,

即, 设 (f[i][j][k]) 为消去区间 (i,j) 内的方块, 并且方块 (j) 一定要和它右边的 (k) 个同色方块 (不包括 (j)) 一起消去时获得的收益.

考虑转移, 我们可以把这 (k+1) 个方块直接消去, 或者在 ([i,j)) 中再枚举一个与 (j) 同色的方块, 把它们一起删去, 所以

1. (f[i][j][k]=f[i][j-1][0]+(k+1)^2)
2. (f[i][j][k]=max{f[i][p][k+1] + f[p+1][j-1][0]}), 且 (p in [i,j), col[p]==col[j])

代码

#include<bits/stdc++.h>
using namespace std;
const int _=200+7;
int T,n,col[_],pre[_],lst[_],f[_][_][_];
void upd(int &x,int y){ x=max(x,y); }
int main(){
  //freopen("x.in","r",stdin);
  cin>>T;
  for(int t=1;t<=T;t++){
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    memset(lst,0,sizeof(lst));
    for(int i=1;i<=n;i++)
      scanf("%d",&col[i]);
    for(int i=1;i<=n;i++){
      pre[i]=lst[col[i]];
      lst[col[i]]=i;
    }
    for(int l=1;l<=n;l++){
      for(int i=1;i+l-1<=n;i++){
	int j=i+l-1;
	for(int k=0;k<=n;k++){
	  upd(f[i][j][k],f[i][j-1][0]+(k+1)*(k+1));
	  int p=pre[j];
	  while(p>=i){
	    upd(f[i][j][k],f[i][p][k+1]+f[p+1][j-1][0]);
	    p=pre[p];
	  }
	}
      }
    }
    printf("Case %d: %d
",t,f[1][n][0]);
  }
  return 0;
}