原题: BZOJ1032 （原题数据有问题）
/*hdu6212[区间dp] 2017青岛ACM-ICPC网络赛*/
#include <bits/stdc++.h>
using namespace std;
int T, n, tot = , kase = ;
char s[];
int dp[][], cnt[], col[];
void solve() {
memset(dp, 0x3f, sizeof(dp));
tot = ;
n = strlen(s);
cnt[tot] = , col[tot] = s[] - '';
for (int i = ; i < n; i++) {
if (s[i] == s[i - ]) cnt[tot]++;
else {
cnt[++tot] = ;
col[tot] = s[i] - '';
}
}
n = tot;
for (int i = ; i <= n; i++) dp[i][] = cnt[i] >= ? : ;
for (int j = ; j <= n; j++) {
for (int i = ; i + j - <= n; i++) {
if (col[i] == col[i + j - ]) {
if (cnt[i] + cnt[i + j - ] < ) {
dp[i][j] = dp[i + ][j - ] + (cnt[i] + cnt[i + j - ] == );
for (int k = ; k < j; k++) {
if (col[i + k - ] == col[i] && cnt[i + k - ] == ) {
dp[i][j] = min(dp[i][j], dp[i + ][k - ] + dp[i + k][j - k - ]);
}
}
}
else dp[i][j] = dp[i + ][j - ];
}
for (int k = ; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[i + k][j - k]);
}
}
}
printf("Case #%d: %d\n", kase++, dp[][n]);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%s", s);
solve();
}
return ;
}
// 011011100000001010101110011000 ans=4
// 10110011001101 ans=3