[PKU1390]Blocks

据说这题是十分经典的动态规划，题目的意思就是求一种消除方块的方法，使得得分最高。

看到这题有种用区间动归的冲动，用f[l,r]记录从l个方块合并到r的最高得分。不过这题消除方块有个限制条件，就是一次必须消除连续的相同颜色的方块，直接操作容易违背这个条件，因此考虑要把方块缩点：用(color[i],len[i])记录有len[i]个color[i]色的方块。这样f[l,r]就表示从第l组色块到第r组色块合并的最有值。

不过有个问题，考虑如下序列：0001111000，把1111拿走后，前后的000 000合并时必须一次完成。但实际上，在程序中根本无法知道1111被拿走了（或者说，如果知道了1111被拿走了，那么要手动合并000 000，也就是要更改(color[i],len[i])，这样会破坏整个数据结构，有有后效性）。

不能在(color[i],len[i])上作修改，那就只能对动归的状态进行修改了：用f[i,j,k]表示合并色块[i,j]，连同色块j之后k个与j同色的方块得到的最高得分。

实际上这个表示方法不需要考虑色块j之后的色块是否合并、颜色是否相同，只需要考虑色块j后有k个和它颜色相同的方块。因为我们可以假设j之后的、夹在色块j和后面的和j同色的方块之间的色块已经被消除。因此就有如下的转移方法：
  1. 如果色块j连同后面的k个方块一起合并掉，那么f[i,j,k]=f[i,j-1]+(len[j]+k)2。
  2. 如果色块j被前面的合并掉了（也就是被前面的某个j’当作是k个方块之一），那么就要找到前面的所有和j一样颜色的x，先把[i,x]连同j合并了，然后再把x和j中间的方块处理掉，f[i,j,k]=min{f[i,x,len[x]+k]+f[x+1,j-1,0]}

答案就是f[1,n,0]。直接写DP可能不好写，因此可以考虑记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
#include <cstring>
using namespace std;

int T,n,_f[201][201][201],color[201],len[201];
int f(const int x,const int y,const int k) {
  if (_f[x][y][k]!=-1)
    return _f[x][y][k];
  int Max=f(x,y-1,0)+(len[y]+k)*(len[y]+k);
  for (int i=x;i<y;++i)
    if (color[i]==color[y])
      Max=max(Max,f(x,i,len[i]+k)+f(i+1,y-1,0));
  return _f[x][y][k]=Max;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>T;
  for (int test=1;test<=T;++test) {
    memset(_f,255,sizeof(_f));
    n=0;
    int m,x,last=-1;
    cin>>m;
    for (int i=1;i<=m;++i) {
      cin>>x;
      if (x!=last) color[++n]=x,len[n]=0;
      ++len[n];
    }
    for (int i=1;i<=n;++i) _f[i][i-1][0]=0;
    cout<<"Case "<<test<<": "<<f(1,n,0)<<endl;
  }
}

Comments