UVa 11584

题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2631&mosmsg=Submission+received+with+ID+26601301

先 (dp) 预处理一下字串是不是回文串，再 (dp) 算最少划分即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1010;

int T, n;

int dp[maxn], is[maxn][maxn];
char s[maxn];

int main(){
	scanf("%d", &T);
	while(T--){
		memset(is, 0, sizeof(is)); 
		scanf("%s", s + 1);
		n = strlen(s + 1);
		
		for(int i = 0 ; i <= n ; ++i) is[i][i] = 1, is[i+1][i] = 1;
		for(int l = 2 ; l <= n ; ++l){
			for(int i = 1 ; i+l-1 <= n ; ++i){
				int j = i + l - 1;
				is[i][j] = is[i+1][j-1] && (s[i] == s[j]);
			}
		}
		
		memset(dp, 0x3f, sizeof(dp));
		dp[0] = 0;
		
		for(int i = 1 ; i <= n ; ++i){
			for(int j = 0 ; j < i ; ++j){
				if(is[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1);
			}
		}
		
		printf("%d
", dp[n]);
	}
	return 0;
}