区间DP UVA 11584 Partitioning by Palindromes-白红宇

区间DP UVA 11584 Partitioning by Palindromes

阅读量：6882 次

发布时间：2019-06-27

本文共 1163 字，大约阅读时间需要 3 分钟。

1 /* 2     题意：给一个字符串，划分成尽量少的回文串 3     区间DP：状态转移方程：dp[i] = min (dp[i], dp[j-1] + 1); dp[i] 表示前i个字符划分的最少回文串， 4             如果s[j] 到 s[i]是回文串，那么可以从dp[j-1] + 1递推过来 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 using namespace std;11 12 const int MAXN = 1e3 + 10;13 const int INF = 0x3f3f3f3f;14 int dp[MAXN];15 char s[MAXN];16 17 bool ok(int l, int r)   {18     while (l < r)   {19         if (s[l] != s[r])   return false;20         l++;    r--;21     }22     return true;23 }24 25 int main(void)  {       //UVA 11584 Partitioning by Palindromes26     int T;  scanf ("%d", &T);27     while (T--) {28         scanf ("%s", s + 1);29         int len = strlen (s + 1);30         memset (dp, 0, sizeof (dp));31         for (int i=1; i<=len; ++i)  {32             dp[i] = i;33             for (int j=1; j<=i; ++j) {34                 if (ok (j, i))  {35                     dp[i] = min (dp[i], dp[j-1] + 1);36                 }37             }38         }39 40         printf ("%d\n", dp[len]);41     }42 43     return 0;44 }