首页 > 代码库 > HDU 5904 LCIS DP
HDU 5904 LCIS DP
http://acm.hdu.edu.cn/showproblem.php?pid=5904
给定两个序列，要求算出其最长的公共上升子序列，
并且这个子序列公差是1.
考虑dp
dpa[val]表示在a数组中，以val这个数字结尾，最长上升1的子序列。dpa[val] = dpa[val - 1] + 1
同理dpb[val]
然后，对于每个相同的数字，需要取min(dpa[val], dpb[val])即可。
如果dpa[5] = 3是这个序列，3 4 5
然后dpb[5] = 5是这个序列 1 2 3 4 5
那么公共部分就是他们的最小值。
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 100000 + 20;int a[maxn];int b[maxn];int dpa[maxn];int dpb[maxn];void work() { memset(dpa, 0, sizeof dpa); memset(dpb, 0, sizeof dpb); int n, m; int mx = -inf; scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); mx = max(mx, a[i]); } int mx2 = -inf; for (int i = 1; i <= m; ++i) { scanf("%d", &b[i]); mx2 = max(mx2, b[i]); } mx = min(mx, mx2); dpa[a[1]] = 1; for (int i = 2; i <= n; ++i) { dpa[a[i]] = dpa[a[i] - 1] + 1; } dpb[b[1]] = 1; for (int i = 2; i <= m; ++i) { dpb[b[i]] = dpb[b[i] - 1] + 1; } int ans = -inf; for (int i = 1; i <= mx; ++i) { ans = max(ans, min(dpa[i], dpb[i])); } printf("%d\n", ans); return ;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf("%d", &t); while (t--) work(); return 0;}
HDU 5904 LCIS DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。