祖玛游戏

祖玛游戏。给你一个长度为 n 的 0、1 串。每一次你可以在一处加入若干个球,如果此处超过三个球,则他们会消失。两端的球将会合并,若合并出球超
过三个则又会消失。我们的目标是将串全部删光。问我们至少添加多少个点。

这道题可以区间dp做,具体见http://blog.csdn.net/hanzheng992/article/details/54743566..

上代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int maxn=205, INF=1e8;
 6 char s[maxn];
 7 int t;
 8 int ziplen, type[maxn], length[maxn];
 9 int dp[maxn][maxn];
10 
11 inline int solve(){
12     for (int i=0; i<ziplen; ++i)
13         dp[i][i]=3-length[i]>0?3-length[i]:1;
14     int tmp;
15     for (int i=1; i<ziplen; ++i){
16         for (int j=0; j<ziplen-i; ++j){
17             dp[j][j+i]=INF;
18             for (int k=j; k<j+i; ++k){
19                 tmp=dp[j][k]+dp[k+1][j+i];
20                 if (tmp<dp[j][j+i]) dp[j][j+i]=tmp;
21             }
22             if (type[j]==type[j+i]){
23                 int flag=0;
24                 if (length[j]+length[j+i]<3) flag=1;
25                 tmp=dp[j+1][j+i-1]+flag;
26                 if (tmp<dp[j][j+i]) dp[j][j+i]=tmp;
27                 if (length[j]==1||length[j+i]==1){ //bug
28                     for (int k=j+1; k<j+i-1; ++k)
29                         if (type[k]==type[j]&&length[k]==1){
30                             tmp=dp[j+1][k-1]+dp[k+1][j+i-1];
31                             if (tmp<dp[j][j+i]) dp[j][j+i]=tmp;
32                         }
33                 }
34             }
35         }
36     }
37     return dp[0][ziplen-1];
38 }
39 
40 int main(){
41     scanf("%d", &t);
42     int len;
43     for (int tt=0; tt<t; ++tt){
44         scanf("%s", s);
45         len=strlen(s);
46         int j=1;
47         ziplen=0;
48         for (int i=1; i<len; ++i){
49             if (s[i]==s[i-1]) ++j;
50             else {
51                 type[ziplen]=s[i-1];
52                 length[ziplen]=j;
53                 j=1;
54                 ++ziplen;
55             }
56         }
57         type[ziplen]=s[len-1];
58         length[ziplen]=j;
59         ++ziplen;
60         printf("Case #%d: %d
", tt+1, solve());
61     }
62     return 0;
63 }