线性结构上的动态规划。回文串的操作在前五章有过详细的介绍和练习。判断的方法是枚举回文串中点。
因为可能要频繁的查询同一个回文串的各种子串,应该进行预处理,将结果存在数组中备用。有机会试一下dp判断回文串。
动态规划部分,注意好边界,没有什么其他的亮点了
Run Time: 0.132s
#define UVa "LT9-7.11584.cpp" //Partitioning by Palindromes #include<cstdio> #include<cstring> #include<algorithm> using namespace std; //Global Variables. const int maxn = 1000 + 10; int kase, n; int palindrome[maxn][maxn]; int dp[maxn]; //// int main() { scanf("%d", &kase); while(kase --) { char str[maxn]; scanf("%s", str); n = strlen(str); memset(palindrome, 0, sizeof(palindrome)); for(int i = 0; i < n; i ++) { //preprocessing int l = i-1, r = i; while(l >= 0 && r < n && str[l] == str[r]) { palindrome[l][r] = 1; l --; r ++; } l = i-1, r = i+1; while(l >= 0 && r < n && str[l] == str[r]) { palindrome[l][r] = 1; l --; r ++; } } dp[0] = 1; for(int i = 1; i < n; i ++) { dp[i] = dp[i-1] + 1; for(int j = 0; j < i; j ++) { if(palindrome[j][i]) { if(j) dp[i] = min(dp[i], dp[j-1] + 1); else dp[i] = 1; } } } printf("%d\n", dp[n-1]); } return 0; }