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])$。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pll;
const int INF = 0x3f3f3f3f;
const int maxn = +; char s[maxn];
int a[maxn];
int d[maxn][maxn]; int main()
{
//freopen("in.txt","r",stdin);
int T;
int kase = ;
scanf("%d",&T);
while(T--)
{
int tot=;
scanf("%s",s);
a[++tot]=;
int len=strlen(s);
for(int i=;i<len;i++)
{
if(s[i]!=s[i-]) a[++tot]=;
a[tot]++;
}
for(int r=;r<=tot;r++)
for(int i=;i+r-<=tot;i++)
{
int j=i+r-;
if(i==j) d[i][j]=-a[i];
else
{
d[i][j]=*tot;
for(int k=i;k<j;k++) d[i][j]=min(d[i][j],d[i][k]+d[k+][j]);
if((j-i)&) continue;
d[i][j]=min(d[i][j],d[i+][j-]+(a[i]+a[j]==));
if(a[i]+a[j]<)
{
for(int k=i+;k<j;k+=)
if(a[k]==) d[i][j]=min(d[i][j],d[i+][k-]+d[k+][j-]);
}
}
}
printf("Case #%d: %d\n",++kase, d[][tot]);
}
return ;
}