HDU 5904 LCIS (dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5904

题意：

给两个序列，要找他们的最长公共递增子序列，并且这个子序列的值必须是连续的(x,x+1,...,y-1,yx,x+1,...,y−1,y)

这次BC全场最简单的一道题.....

先dp两个序列中易每个数字结尾的最大的连续上升序列的长度。

然后比对两个dp数组，取出每个数字dp值的最小值，然后在这些最小值里取最大的就行了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int maxnn = 1e6 + 7; 
int a[maxn], b[maxn];
int dpa[maxnn], dpb[maxnn];
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n, m;
		scanf("%d %d", &n, &m);
		memset(dpa, 0, sizeof(dpa));
		memset(dpb, 0, sizeof(dpb));
		for(int i = 1; i <= n; i++) {
			scanf("%d", a + i);
			dpa[a[i]] = max(dpa[a[i]], dpa[a[i] - 1] + 1);
		}
		for(int i = 1; i <= m; i++) {
			scanf("%d", b + i);
			dpb[b[i]] = max(dpb[b[i]], dpb[b[i] - 1] + 1);
		}
		int ans = 0;
		if(n < m) {
			for(int i = 1; i <= m; i++) {
				ans = max(ans, min(dpa[b[i]], dpb[b[i]]));
			}
		}
		else {
			for(int i = 1; i <= n; i++) {
				ans = max(ans, min(dpa[a[i]], dpb[a[i]]));
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}