JS's Blog
0%

Hdu 1904 LCIS (dp)

Posted on Edited on In ,

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

题目大意：
给定两个串a,b，长度分别为n与m，求两个串的最长公共上升子序列，且子序列的值连续

n,m≤100000  a[i],b[i]≤1000000n,m\leq100000 \space \space a[i],b[i]\leq1000000

分析：
直接做显然不好做，选择dp[i]表示以i结尾的连续递增子序列的长度，dp[a[i]] = dp[a[i]-1]+1，i从1遍历到n，即可得到一个串的所有子序列，得到两个串的子序列后，遍历每个子序列，两个串的相同结尾的子序列长度取最小值，然后找最大值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;


int a[120000],b[120000],dpa[2100000],dpb[2100000];


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--)
    {
        int maxn = 0 ;
        scanf("%d%d",&n,&m);
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%d",&a[i]);
            maxn = max(maxn,a[i]);
        }
        for (int i = 1 ; i <= m ; i ++)
        {
            scanf("%d",&b[i]);
            maxn = max(maxn,b[i]);
        }
        for (int i = 0 ; i <=maxn ; i ++)
        {
            dpa[i] = 0;
            dpb[i] = 0;
        }
        int ans=0;
        for (int i = 1 ; i <= n ; i ++)
            dpa[a[i]] = dpa[ a[i] - 1 ] + 1 ;
        for (int i = 1 ; i <= m ; i ++)
            dpb[b[i]] = dpb[ b[i] - 1 ] + 1 ;
        for (int i = 0 ; i <= maxn ; i ++)
            ans = max(ans,min(dpa[i],dpb[i]));
        printf("%d\n",ans);
    }
}