题目描述

作为程序员，在工程中需要掌握的技能之一，就是避免代码的重复。  MCC同学开发了一套自动检测重复代码的软件，现在就剩下算法部分未完成了。  我们要求给出两个文件的内容，通过计算其中“最长公共子序列”的长度，来计算其代码重复度。  通过MCC牌黑科技，我们将文件的内容变成了一个整数数组，来便于进行比较。

输入

第一行两个整数n和m 第二行，第三行分别有n，m个整数，表示文件内容。 保证n,m<6000，保证文件内容数字<10000

输出

输出一行整数，表示最长公共子序列的长度。

样例输入

5 7
1 0 2 0 2
2 1 1 1 2 0 0

样例输出

3

这是一个较经典的DP问题。

下面是代码：

#include <iostream>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE 
 freopen("in.txt", "r", stdin);
#endif
 int n, m;
 while (cin >> n >> m)
 {
  int dn[6001], dm[6001];
  short dp[2][6001];
  for (int i = 1; i <= n; i++)
   cin >> dn[i];
  for (int i = 1; i <= m; i++)
   cin >> dm[i];
  for (int i = 0; i < m; i++)
   dp[0][i] = 0;
  int max = 0;
  for (int i = 1; i <= n; i++)
   for (int j = 1; j <= m; j++)
   {
    dp[i % 2][j] = (dp[(i - 1) % 2][j] > dp[i % 2][(j - 1)] ? dp[(i - 1) % 2][j] : dp[i % 2][(j - 1)]);
    if (dn[i] == dm[j])
    {
     dp[i % 2][j] = (dp[(i - 1) % 2][(j - 1)] + 1 > dp[i % 2][j] ? dp[(i - 1) % 2][(j - 1)] + 1 : dp[i % 2][j]);
     max = max > dp[i % 2][j] ? max : dp[i % 2][j];
    }
   }
  cout << max << endl;
 }
 return 0;
}