UVA 10405【LCS】【背包】

本题为 LCS 裸题，请求评橙。

考虑 DP。

状态 $f[i][j]$ 为第一个字符串选到了 $i$，第二个字符串选到了 $j$（位置）。

容易发现，如果第一个字符串 $i$ 位置的字符和第二个字符串 $j$ 位置的字符一样，那么有 $f[i][j]=f[i-1][j-1]+1$，否则有 $f[i][j]=\max (f[i-1][j],f[i][j-1])$。

时间复杂度 $O(n^2)$。

实际上有时间复杂度更好的 $O(n\log n)$ 算法，但是超纲没写。

坑点：有空格，需要使用 getline 读入。

// 这回只花了45min就打完了。
// 真好。记得多手造几组。最好有暴力对拍。

#include 

using namespace std;

int f[2010][2010];

int main()
{
  string s, t;
  while (getline(cin, s), getline(cin, t)) // debug 有可能有空格
  {
    if (cin.eof())
      break;
    int l1 = s.size(), l2 = t.size();
    s = ' ' + s, t = ' ' + t;
    for (int i = 1; i <= l1; i ++)
      for (int j = 1; j <= l2; j ++)
        if (s[i] != t[j])
          f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        else
          f[i][j] = f[i - 1][j - 1] + 1;
    cout << f[l1][l2] << '\n';
  }
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29