HDU 6212 Zuma（区间dp）

http://acm.hdu.edu.cn/showproblem.php?pid=6212

题意：
有一行的祖玛，只由1和0组成，每次出现连续三个及以上的就会消去，问你最少需要发射多少个球才能消完。

思路：
区间最优值问题。先处理一下，把连续相同的放在一起。

对于区间$(i,j)$来说，只有3种情况：

①：把$(i,j)$分成两部分，$d[i][j]=min(d[i][j],d[i][k]+d[k+1][j])$。

②：如果i和j是相同的，那么可以把中间的处理了，然后在合并两端的，$d[i][j]=min(d[i][j],d[i+1][j-1]+(a[i]+a[j]==2))$。

③：如果i和j是相同的，并且两个不同数不同时为2的情况下，可以三个来完成合并，$d[i][j]=min(d[i][j],d[i+1][k-1]+d[k+1][j-1])$。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn = 200+5;
17 
18 char s[maxn];
19 int a[maxn];
20 int d[maxn][maxn];
21 
22 int main()
23 {
24     //freopen("in.txt","r",stdin);
25     int T;
26     int kase = 0;
27     scanf("%d",&T);
28     while(T--)
29     {
30         int tot=0;
31         scanf("%s",s);
32         a[++tot]=1;
33         int len=strlen(s);
34         for(int i=1;i<len;i++)
35         {
36             if(s[i]!=s[i-1]) a[++tot]=0;
37             a[tot]++;
38         }
39         for(int r=1;r<=tot;r++)
40         for(int i=1;i+r-1<=tot;i++)
41         {
42             int j=i+r-1;
43             if(i==j)  d[i][j]=3-a[i];
44             else
45             {
46                 d[i][j]=2*tot;
47                 for(int k=i;k<j;k++)  d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
48                 if((j-i)&1) continue;
49                 d[i][j]=min(d[i][j],d[i+1][j-1]+(a[i]+a[j]==2));
50                 if(a[i]+a[j]<4)
51                 {
52                     for(int k=i+2;k<j;k+=2)
53                         if(a[k]==1) d[i][j]=min(d[i][j],d[i+1][k-1]+d[k+1][j-1]);
54                 }
55             }
56         }
57         printf("Case #%d: %d
",++kase, d[1][tot]);
58     }
59     return 0;
60 }