首页 > 代码库 > 3301 Square words
3301 Square words
3301 Square words
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 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。
分类标签 Tags 点此展开
动态规划 最长公共子序列
题解：
O(n^3)的最长公共子序列，居然过了。
AC代码：
#include<cstdio>#include<string>#include<iostream>using namespace std;const int N=1e3+10;int n,f[N][N];string s;int ans=0x7fffffff; inline int LCS(string a,string b){ int l1=a.length(),l2=b.length(); for(int i=0;i<l1;i++){ for(int j=0;j<l2;j++){ if(!i||!j) f[i][j]=a[i]==b[j]; else{ if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } } } return f[l1-1][l2-1];}int main(){ cin>>n>>s; for(int i=0;i<n-1;i++){ string a,b; for(int j=0;j<=i;j++) a+=s[j]; for(int j=i+1;j<n;j++) b+=s[j]; int anc=LCS(a,b); ans=min(ans,n-2*anc); } printf("%d\n",ans); return 0;}
3301 Square words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。