一道大水题
题目传送门
题目大意
求两个数列的最长公共子序列
思路
可以把LCS问题转化为LIS问题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define M 250*250
#define Inf 1000000000 int s[M], g[M], d[M];
int num[M];int main(){int T;scanf ( "%d", &T);for ( int kase = 1; kase <= T; kase ++){int N, p, q, x;scanf ( "%d%d%d", &N, &p, &q);memset( num ,0, sizeof(num));for ( int i = 1; i <= p+1; i++) scanf( "%d", &x), num[x] = i;int n = 0;for ( int i = 0; i < q+1; i++) { scanf( "%d", &x);if ( num[x] ) s[n++] = num[x]; }for ( int i = 1; i <= n; i++ ) g[i] = Inf;int ans = 0;for ( int i = 0; i < n; i++){int k = lower_bound( g+1, g+1+n, s[i] ) - g;d[i] = k;g[k] = s[i];ans = max( ans, d[i]);} printf( "Case %d: %d\n", kase, ans);}return 0;
}