ACM DP Partitioning by Palindromes

爱被打了一巴掌 2022-06-11 08:47 214阅读 0赞

滴，集训第十六天打卡。

补题路漫漫呀~

uva 11584

Partitioning by Palindromes

20170803154641350

20170803154657355

题目大意：将一个字符串划分成尽量少的回文串

思路：从1-N枚举，有转移方程dp[i+1]=min(dp[i+1],dp[j]+1)。

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  5. int dp[1005];
  6. char a[1005];
  7. bool isp(int l,int r)  
  8. {  
  9.      for(int k=0;k*2<=r-l;k++)  
  10.      {  
  11.          if(a[l+k]!=a[r-k])   
  12.          return false; 
  13.      }  
  14.      return true;  
  15. }  
  16. int main()
  17. {
  18.     int n,b,i,j;    
  19.     scanf("%d",&n);
  20.     while(n--)
  21.     {
  22.         scanf("%s",a);
  23.         b=strlen(a);
  24.         for(i=0;i<b;i++)
  25.         dp[i]=99999999;
  26.         dp[0]=0;dp[1]=1;
  27.          for(i=1;i<b;i++)  
  28.         {   
  29.             dp[i+1]=99999999;
  30.             for(j=i;j>=0;j--)  
  31.             {  
  32.                 if(isp(j,i))
  33.                 dp[i+1]=min(dp[i+1],dp[j]+1);  
  34.             }  
  35.         }  
  36.         printf("%d\n",dp[b]);
  37.     }
  38. }

发表评论

表情：
评论列表 （有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读