[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[2][10008],len,len1; char s[10008],s1[10008]; int main(){ scanf("%s",s); scanf("%s",s1); len=strlen(s); len1=strlen(s1); int x=0,y; for(int i=0;i<len;i++){ x=1-x; y=1-x; for(int j=0;j<len1;j++) if(s[i]==s1[j]) dp[x][j+1]=dp[y][j]+1; else dp[x][j+1]=max(dp[x][j],dp[y][j+1]); } printf("%d",dp[x][len1]); }