[AHOI2004]奇怪的字符串
题目描述
输入输出格式
输入格式：
输入文件中包含两个字符串X和Y。当中两字符串非0即1。序列长度均小于9999。
输出格式：
X和Y的最长公共子序列长度。
输入输出样例
输入样例#1：
01010101010 00000011111
输出样例#1：
6
输入样例#2：
01011 010010101111111111
输出样例#2：
5 -_-||，题目直接告诉你求最长公共子序列；
只需用一下滚动数组省点空间就行了；
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std; int n,dp[][],len,len1;
char s[],s1[]; int main(){
scanf("%s",s);
scanf("%s",s1);
len=strlen(s);
len1=strlen(s1);
int x=,y;
for(int i=;i<len;i++){
x=-x; y=-x;
for(int j=;j<len1;j++)
if(s[i]==s1[j]) dp[x][j+]=dp[y][j]+;
else dp[x][j+]=max(dp[x][j],dp[y][j+]);
}
printf("%d",dp[x][len1]);
}