題意：給定一個字符串，把該字符串劃分為最少的回文串。

思路：dp，到達i點的回文串長度都存起來，那么dp[i]=min(以i為結尾的最短的回文串長度）。

code：

#include <bits/stdc++.h> using namespace std;#define ft(i,s,t) for (int i=s;i<=t;i++) #define cls(v,c) memset(v,c,sizeof(v)) const int N=1005; const int INF=0x3f3f3f3f;char s[N]; int len,d[N]; vector<int>v[N];void sol() {cls(d,INF);ft(i,0,N) v[i].clear();s[0]='%';len=strlen(s),len--;ft(i,2,len-1){int j=1;while (s[i-j]==s[i+j]){v[i+j].push_back(i-j);j++;}}ft(i,1,len-1){int j=0;while (s[i-j]==s[i+1+j]){v[i+1+j].push_back(i-j);j++;}}} int main() {int T;scanf("%d",&T);while (T--){scanf("%s",s+1);sol();d[0]=0;ft(i,1,len){d[i]=d[i-1]+1;for (int j=0;j<v[i].size();j++){int k=v[i][j];d[i]=min(d[i],d[k-1]+1);}}printf("%d\n",d[len]==0?1:d[len]);} }

總結

以上是生活随笔為你收集整理的uva 11584——Partitioning by Palindromes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。