題意：劃分回文串，求出一個(gè)字符串的最小回文串個(gè)數(shù)。

#include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<stdio.h> #include<string> using namespace std;int s[1000 + 10][1000 + 10]; string str;void init() {for (int i = 0; i < str.length(); i++) {int l = i, r = i;while (l >= 0 && str[l] == str[r]) {s[l][r] = 1;l--; r++;}l = i, r = i+1;while (l>=0&&str[l] == str[r]) {s[l][r] = 1;l--; r++;}} } int d[1010]; void dp() {for (int i = 0; i < str.length(); i++) {if(i>0)d[i] = d[i - 1] + 1;else d[0] = 1;for (int j = -1; j < i; j++) {if (s[j+1][i]) {if (j == -1)d[i] = 1;elsed[i] = min(d[i], d[j] + 1);}}} } int main() {int n;while (cin >> n && n) {for (int i = 0; i < n; i++) {cin >> str;memset(d, 0, sizeof(d));memset(s, 0, sizeof(s));init();dp();cout << d[str.length() - 1] << endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的uva11584的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。