51 nod 1154(プッシュ)
1415 ワード
リンク:クリックしてリンクを開く
題意:1つの文字列Sがあって、Sが少なくとも何個の回文列に分けられることができることを求めます例えば:
abbaabaaには、様々な区分があります
a|bb|aaba-3個の回文列a|bb|a|aba|a-5個の回文列a|b|a|b|a|b|a|a|a|a|a-8個の回文列
このうち第1区分方式の区分数が最も少ない
コード:
題意:1つの文字列Sがあって、Sが少なくとも何個の回文列に分けられることができることを求めます例えば:
abbaabaaには、様々な区分があります
a|bb|aaba-3個の回文列a|bb|a|aba|a-5個の回文列a|b|a|b|a|b|a|a|a|a|a-8個の回文列
このうち第1区分方式の区分数が最も少ない
コード:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
char s[5005];
int vis[5005][5005],dp[5005];
int main(){
int i,j,len;
while(scanf("%s",s+1)!=EOF){ //dp[i] i
len=strlen(s+1); //dp[i]=min(dp[i],dp[j]+1),j<=i&&j i
for(i=1;i<=len;i++)
dp[i]=i,vis[i][i]=1;
for(i=1;i<=len;i++){
for(j=1;j<=i;j++){
if(j==i)
dp[i]=min(dp[i],dp[j-1]+1);
else if(j==i-1&&s[j]==s[i]){ // 1 2
vis[j][i]=1;
dp[i]=min(dp[i],dp[j-1]+1);
}
else if(vis[j+1][i-1]&&s[j]==s[i]){
vis[j][i]=1;
dp[i]=min(dp[i],dp[j-1]+1);
}
}
}
printf("%d
",dp[len]);
}
return 0;
}