首页 > 代码库 > uva 11584

uva 11584

2024-07-19 10:35:51   221人阅读

这题说的是给了长度为n的字符串， 将这个字符串分成k个子串，求使得这个k尽量的小的最小值，当这个长度为n的字符串本身就是回文串的时候，那么k为1。

考虑第i个字符和前i-1个中的第j个搭配形成回文子串，开一个数组标记一下就可以知道了这个从j到i是否是回文子串然后，每次取最小，我们发现这样是一个最优的子结构然后 我们推出 dp[i]= min(dp[j-1]+1){str[i] 与str[j]之间形成了回文串的j};

#include <iostream>#include <cstdio>#include <algorithm>#include <string.h>#include <cmath>using namespace std;const int maxn=1005;const int INF = 10000000;int dp[maxn],Len;bool vis[maxn][maxn];void inti(){   for(int i =0; i<=Len;  i++)     for( int j =i+1; j <=Len ; ++j )      vis[i][j]=false;}char str[maxn];int main(){     int cas;     for( int i =0; i<= 1000; i++ )        for(int j=0 ; j<=i; j++)            vis[i][j] = true;        scanf("%d",&cas);     for(int cc=1; cc<= cas; ++ cc){         scanf("%s",str+1);         Len = strlen(str+1);         dp[0]=0;         inti();         for(int i =1; i<=Len; ++i){              dp[i]=dp[i-1]+1;              for(int j =1; j<i; ++j )              if(str[i]==str[j]&&vis[j+1][i-1]==true){                   vis[j][i]=true;                   dp[i]=min(dp[j-1]+1,dp[i]);              }         }         printf("%d\n",dp[Len]);     }     return 0;}
View Code

 

uva 11584


联系
我们