首页 > 代码库 > Partitioning by Palindromes

Partitioning by Palindromes

2024-07-10 15:26:25   213人阅读

uva11584:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2631

题意：给你一个串，问你这个串最少被划分成多少个子串，才能使得每个子串都是回文子串。

题解：一开始不知道用什么方法来解题，回来才知道是DP。状态方程：f【i】，表示从0到i，至少被划分的子串个数。转移方程f【i】=min（f【i-1】+1，f【j-1】+1)(其中j表示，从j到i之间的字母构成回文串)，然后枚举满足条件的j，最后的答案就是f【len-1】。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int f[1003]; 7 char str[1002]; 8 bool check(int x,int y){//判断是不是回文串 9     while(x<y){10         if(str[y]!=str[x])return false;11         x++;12         y--;13     }14    return true;15 }16 int main(){17     int T;18     scanf("%d",&T);19       while(T--){20         scanf("%s",str);21           memset(f,0,sizeof(f));22           int len =strlen(str);23           f[0]=1;24           for(int i=1;i<len;i++){25             f[i]=f[i-1]+1;26             for(int j=i-1;j>=0;j--){27                 if(str[j]==str[i]){28                     if(check(j,i)){29                         f[i]=min(f[i],f[j-1]+1);30                     }31                 }32              }33           }34        printf("%d\n",f[len-1]);35       }36 }
View Code

 


联系
我们