当前位置: 代码迷 >> 综合 >> HDU 5904 - LCIS
  详细解决方案

HDU 5904 - LCIS

热度:78   发布时间:2023-12-24 11:17:03.0

题目大意:求序列a与序列b的最大连续公共子序列。

解题思路:动态规划,a[temp]表示序列a以temp为末端的最长连续增大序列的长度。a[temp] = a[temp-1] + 1,这是由于输入序列a第一个数时,以这个数为末端的最长连续增大序列的长度肯定为1,之后序列a中的数,根据记录过temp-1的长度基础+1,如果没有记录过自然也是1,否则则是记录时的长度加1。这就是基于连续的规律。结果就根据序列b记录时每次判断,对应序列a中,以temp为末端的最长连续增大序列。

ac代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int t, a[1000005], b[1000005], n, m, ans, temp;
int main()
{scanf("%d", &t);while (t--){scanf("%d%d", &n, &m);ans = 0;memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));for (int i = 1; i <= n; i++){scanf("%d", &temp);a[temp] = a[temp - 1] + 1;}for (int i = 1; i <= m; i++){scanf("%d", &temp);b[temp] = b[temp - 1] + 1;ans = max(ans, min(a[temp], b[temp]));}printf("%d\n", ans);}return 0;
}