题目描述
输入输出格式
输入格式:
输入文件中包含两个字符串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]);
- }
posted @2017-09-24 20:05 为你献上依米花阅读(...) 评论(...)编辑 收藏