首页 > 代码库 > HDU 5904 - LCIS (BestCoder Round #87)
HDU 5904 - LCIS (BestCoder Round #87)
HDU 5904 - LCIS [ DP ] BestCoder Round #87
题意：
给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的
分析：
状态转移方程式： dp[a[i]] = max(dp[a[i]], dp[a[i]-1] + 1);
发现其实可以简化为 dp[a[i]] = dp[a[i]-1] + 1；因为计算过程中dp[a[i]]不会降低
对两个序列都求一遍，然后取两者最小值的最大值
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 const int MAXM = 1000005; 7 const int MAXN = 1000005; 8 int t, n, m; 9 int a[MAXN], b[MAXN];10 int dp1[MAXM], dp2[MAXM];11 int main()12 {13 scanf("%d", &t);14 while (t--)15 {16 scanf("%d%d", &n, &m);17 memset(dp1, 0, sizeof(dp1));18 memset(dp2, 0, sizeof(dp2));19 int top = 0;20 for (int i = 1; i <= n; i++)21 {22 scanf("%d", &a[i]);23 dp1[a[i]] = dp1[a[i]-1] + 1;24 top = max(top, a[i]);25 } 26 for (int i = 1; i <= m; i++)27 {28 scanf("%d", &b[i]);29 dp2[b[i]] = dp2[b[i]-1] + 1;30 top = max(top, b[i]);31 } 32 int ans = 0;33 for (int i = 1; i <= top; i++) ans = max(ans, min(dp1[i], dp2[i]));34 printf("%d\n", ans);35 } 36 }
HDU 5904 - LCIS (BestCoder Round #87)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。