首页 > 代码库 > UVa 11584 划分成回文串

UVa 11584 划分成回文串

2024-09-02 21:26:35   216人阅读

https://vjudge.net/problem/UVA-11584

题意：

给出一串字符，把它划分成尽量少的回文串。

思路：

用d[i]表示划分到i时所能划分的最小个数，转移方程为d[i]=min{d[i],d[j]+1},当然前提是j+1~i是回文串，我们可以预处理计算出所有的回文串，这样转移时就比较方便。

 1 #include<iostream>  2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6  7 const int maxn = 1000 + 10; 8  9 int ans[maxn][maxn];10 char a[maxn];11 int d[maxn];12 13 int main()14 {15     //freopen("D:\\txt.txt", "r", stdin);16     int t;17     cin >> t;18     while (t--)19     {20         memset(ans, 0, sizeof(ans));21         memset(d, 0, sizeof(d));22         cin >> a+1;23         int l = strlen(a+1);24 25         //打表，判断i~j是否是回文串26         for (int i = 1; i <= l; i++)27         {28             for (int j = i; j <= l; j++)29             {30                 int left = i, right = j;31                 int ok = 1;32                 while (left <= right)33                 {34                     if (a[left] != a[right])35                     {36                         ok = 0;37                         break;38                     }39                     left++;40                     right--;41                 }42                 if (ok)  ans[i][j] = 1;43             }44         }45 46         d[0] = 0;47         for (int i = 1; i <= l; i++)48         {49             d[i] = d[i-1]+1;     50             for (int j = 1; j <= i; j++)51             {52                 if (ans[j][i])    53                 d[i] = min(d[i], d[j-1] + 1);54             }55         }56         cout << d[l] << endl;57     }58     return 0;59 }

 

UVa 11584 划分成回文串


联系
我们