【14.06%】【hdu 5904】LCIS
2024-08-31 21:21:23
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 519 Accepted Submission(s): 238
Problem Description
Alex has two sequences a1,a2,...,an and b1,b2,...,bm.
He wants find a longest common subsequence that consists of consecutive values in increasing order.
He wants find a longest common subsequence that consists of consecutive values in increasing order.
Input
There are multiple test cases. The first line of input contains an integer T,
indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n,m≤100000) --
the length of two sequences. The second line contains n integers: a1,a2,...,an (1≤ai≤106).
The third line contains n integers: b1,b2,...,bm (1≤bi≤106).
There are at most 1000 test
cases and the sum of n and m does
not exceed 2×106.
indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n,m≤100000) --
the length of two sequences. The second line contains n integers: a1,a2,...,an (1≤ai≤106).
The third line contains n integers: b1,b2,...,bm (1≤bi≤106).
There are at most 1000 test
cases and the sum of n and m does
not exceed 2×106.
Output
For each test case, output the length of longest common subsequence that consists of consecutive values in increasing order.
Sample Input
3
3 3
1 2 3
3 2 1
10 5
1 23 2 32 4 3 4 5 6 1
1 2 3 4 5
1 1
2
1
Sample Output
1
5
0
Source
【题解】
设q[i],表示以数字i为上升序列的最后一个元素的最长长度。
则if (q[i-1] == 0)
q[i-1] = 1;
else
q[i] = max(q[i-1]+1,q[i]);
最后枚举要枚举n+m个而不是枚举1..100W,不然会超时。
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; const int MAXN = 102001;
const int MAX_NUM = 1009999; int n,m,a[MAXN],b[MAXN],q1[MAX_NUM],q2[MAX_NUM]; void input_data()
{
scanf("%d%d", &n,&m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (q1[a[i]-1] == 0)
q1[a[i]] = 1;
else
if (q1[a[i]] < q1[a[i]-1]+1)
q1[a[i]] = q1[a[i] - 1] + 1;
}
for (int i = 1; i <= m; i++)
{
scanf("%d", &b[i]);
if (q2[b[i] - 1] == 0)
q2[b[i]] = 1;
else
if (q2[b[i]] < q2[b[i] - 1] + 1)
q2[b[i]] = q2[b[i] - 1] + 1;
}
} void get_ans()
{
int len = 0;
for (int i = 1; i <= n; i++)//枚举的是出现过的每个数字
{
int d = min(q1[a[i]], q2[a[i]]);
if (d > len)
len = d;
}
for (int i = 1; i <= m; i++)
{
int d = min(q1[b[i]], q2[b[i]]);
if (d > len)
len = d;
}
printf("%d\n", len);
} void init()
{
for (int i = 0; i <= 1000000; i++)
q1[i] = 0;
for (int i = 0; i <= 1000000; i++)
q2[i] = 0;
} int main()
{
// freopen("F:\\rush.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
init();
input_data();
get_ans();
}
return 0;
}
最新文章
- [LeetCode] One Edit Distance 一个编辑距离
- linux性能监控工具
- postgresql 函数&;存储过程 ; 递归查询
- windows重新获取IP
- sql 两列相加存到另一列
- C程序(3)
- ubuntu11.10(TQ210)下移植boa服务器
- delegate实现Javascript的each方法
- release management客户端无法连接到release management server的问题解决
- iframe子页面调用父页面javascript函数的方法
- 菜鸟容易中的招__setattr__
- pyinstaller深入使用,打包指定模块,打包静态文件
- 配置国内 Docker Registry Mirror
- 使用jquery.mCustomScrollbar自定义滚动条(2)
- Processing支持中文显示
- python内存泄漏
- Web层的Controller代码逻辑
- 提高C#编程水平的50个要诀
- 《springcloud 四》服务保护机制
- POJ 1144 Network(割点)