首页 > 代码库 > Square words（codevs 3301）
Square words（codevs 3301）
题目描述 Description
定义square words为：
1.长度为偶数。
2.前一半等于后一半。
比如abcabc和aaaa都是square words，但是abcabcab和aaaaa都不是。
现在有一个长度为n的字符串，求至少要删掉多少个字符，使得剩下的字符串是square words。
输入描述 Input Description
第一行包含一个正整数n。
第二行一个长度为n的字符串，仅包含小写字母
输出描述 Output Description
仅包含一个整数，表示最少需要删掉的字符数
样例输入 Sample Input
11
abaccdaabcd
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例说明】
abaccdaabcd
【数据规模】
对于40%的数据，n ≤ 20；
对于100%的数据，n ≤ 500。
/* ，枚举断点，求最长公共子序列*/#include<cstdio>#include<cstring>#include<iostream>#define M 510using namespace std;char s[M],a[M],b[M];int n,n1,n2,f[M][M],ans;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) cin>>s[i]; for(int k=1;k<n;k++) { memset(f,0,sizeof(f)); n1=0,n2=0; for(int i=1;i<=k;i++) a[++n1]=s[i]; for(int i=k+1;i<=n;i++) b[++n2]=s[i]; for(int i=1;i<=n1;i++) for(int j=1;j<=n2;j++) { if(a[i]==b[j])f[i][j]=max(f[i-1][j-1]+1,f[i][j]); f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1])); ans=max(ans,f[i][j]); } } printf("%d",n-ans*2); return 0;}
Square words（codevs 3301）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。