网站新闻源码,上海浦东人才市场招聘会,课程网站建设的财务分析,网站源码绑定域名处理题目
题目描述 题意#xff1a;
X和Y两个字符串#xff0c;两个字符串各取子序列X1和Y1#xff0c;问X1Y1的情况下X1和Y1的长度和最长是多少#xff1f; 比如例子#xff1a; zazxwabzczazazd abcaa
第一个字符串选取子序列为azxwabzczazazd 第二个为bcaa azxwabzc…题目
题目描述 题意
X和Y两个字符串两个字符串各取子序列X1和Y1问X1Y1的情况下X1和Y1的长度和最长是多少 比如例子 zazxwabzczazazd abcaa
第一个字符串选取子序列为azxwabzczazazd 第二个为bcaa azxwabzczazazd bcaa
题解
一开始我就开始犯懵不同长度的字符串怎么比较。。。 aaaaa 我一开始着重点都放在lcs上但是怎么处理也不到位。。 最后看题解发现自己只走对了一半
假设删完的字符串是x和y因为xy所以要么x是y的前缀要么存在以为i是的xiyi只有这两种情况是是的xy 那么我们可以用lcs求出最长公共子序列的长度 如果x是y的前缀那求出的长度也就是x的长度答案就是max(lcs(i,j)*2(m-j)),m是y的长度 如果是第二情况那么存在一个i和j是的sitj. 枚举i和j求max( lcm(i-1,j-1) 2 (n-i ) (m-j) 2) 时间复杂度O(nm)
代码
/*
zazxwabzczazazd
abcaa
*/
#includeiostream
#includecstdio
#includecstring
using namespace std;
const int N2005;
int n,m;
int f[N][N];
char a[N],b[N];
int main(){while(~scanf(%s%s,a1,b1)){int nstrlen(a1);int mstrlen(b1); for(int i0;in;i){for(int j0;jm;j){f[i][j]0;}}for(int i1;in;i){for(int j1;jm;j){f[i][j]max(f[i-1][j],f[i][j-1]);if(a[i]b[j])f[i][j]max(f[i][j],f[i-1][j-1]1);}}int ans0;ansm;for(int i1;in;i){for(int j1;jm;j){ansmax(ans,f[i][j]*2m-j);if(a[i]b[j]){ansmax(ans,f[i-1][j-1]*2n1-im1-j);}}}printf(%d\n,max(ans,f[n][m]*2));
}return 0;
}
