UVA 10405【LCS】【背包】
本题为 LCS 裸题，请求评橙。
考虑 DP。
状态 f [ i ] [ j ] f[i][j] f[i][j] 为第一个字符串选到了 i i i，第二个字符串选到了 j j j（位置）。
容易发现，如果第一个字符串 i i i 位置的字符和第二个字符串 j j j 位置的字符一样，那么有 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j] = f[i - 1][j - 1] + 1 f[i][j]=f[i−1][j−1]+1，否则有 f [ i ] [ j ] = max ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j] = \max(f[i - 1][j], f[i][j - 1]) f[i][j]=max(f[i−1][j],f[i][j−1])。
时间复杂度 O ( n 2 ) O(n^2) O(n2)。
实际上有时间复杂度更好的 O ( n log n ) O(n\log n) O(nlogn) 算法，但是超纲没写。
坑点：有空格，需要使用 getline 读入。
// 这回只花了45min就打完了。
// 真好。记得多手造几组。最好有暴力对拍。
#include <bits/stdc++.h>
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;
}