UVA 11584—— Partitioning by Palindromes

题意：给定一个串，然后问最少可以分割成多少个回文串。

思路：简单dp，dp[i]=min(dp[j]+1,1<j<=i),两次循环扫一遍即可，考察dp的思想。

code：

#include <bits/stdc++.h> using namespace std;const int N=1005;char s[N]; int dp[N];bool ok(int l,int r) {while (r>l){if (s[l]!=s[r]) return 0;r--,l++;}return 1; } int main() {int T;scanf("%d",&T);while (T--){scanf("%s",s+1);int len=strlen(s+1);memset(dp,0,sizeof(dp));for (int i=1;i<=len;i++){dp[i]=i+1;for (int j=1;j<=i;j++)if(ok(j,i))dp[i]=min(dp[j-1]+1,dp[i]);}printf("%d\n",dp[len]);} }

总结

以上是生活随笔为你收集整理的UVA 11584—— Partitioning by Palindromes的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。