题目

题目描述

题意：

X和Y两个字符串，两个字符串各取子序列X1和Y1，问X1<=Y1的情况下X1和Y1的长度和最长是多少？
比如例子：
zazxwabzczazazd
abcaa

第一个字符串选取子序列为azxwabzczazazd
第二个为bcaa
azxwabzczazazd < bcaa

题解：

一开始我就开始犯懵，不同长度的字符串怎么比较。。。
aaa>aa
我一开始着重点都放在lcs上，但是怎么处理也不到位。。
最后看题解发现自己只走对了一半

假设删完的字符串是x和y，因为x<=y，所以要么x是y的前缀，要么存在以为i是的xi<yi，只有这两种情况是是的x<=y
那么我们可以用lcs求出最长公共子序列的长度
如果x是y的前缀，那求出的长度也就是x的长度，答案就是max(lcs(i,j)*2+(m-j)),m是y的长度
如果是第二情况，那么存在一个i和j，是的si<tj.
枚举i和j，求max( lcm(i-1,j-1) 2 +(n-i ) + (m-j) +2)
时间复杂度O(nm)

代码：

/* zazxwabzczazazd abcaa */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2005;
int n,m;
int f[N][N];
char a[N],b[N];
int main(){
   
	
	while(~scanf("%s%s",a+1,b+1)){
   
	
	int n=strlen(a+1);
	int m=strlen(b+1); 
	for(int i=0;i<=n;i++){
   
		for(int j=0;j<=m;j++){
   
			f[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
   
		for(int j=1;j<=m;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 ans=0;
	ans=m;
	for(int i=1;i<=n;i++){
   
		for(int j=1;j<=m;j++){
   
			ans=max(ans,f[i][j]*2+m-j);
			if(a[i]<b[j]){
   
				ans=max(ans,f[i-1][j-1]*2+n+1-i+m+1-j);
			}
		}
	}
	printf("%d\n",max(ans,f[n][m]*2));
}
	return 0;
}