「HZOI 2016」最长公共上升子序列

Description

求两个序列的最长公共上升子序列.

Input

第一行一个整数n,第二行n个整数Ni 即第一个序列,第三行一个整数m,第四行m个整数Mi 即第二个序列.
n ≤1000,m ≤1000,0 ≤ Ni,Mi ≤1000

Output

maxlen 为最长公共上升子序列的长度

Sample Input

5
1 4 2 5 12
4
12 1 2 4

Sample Output

2

Solution

一开始的错解:
由于看到Ni,Mi是非常小的,于是想到用桶把M序列中每个数字的位置记下来,在N中直接找上升子序列并且需满足由f[j]转移过来的a[j]在M序列中的位置<=i.后去交,发现数字可以重复2333.又想到记一最小位置,记一最大位置,还是不行,只好作罢.

正解:

if(a[i]>b[j])maxx=max(maxx,f[j]);
if(a[i]==b[j])f[j]=maxx+1;

很巧妙,两层循环N,M,把两个序列相互比较,等到在某个序列中找到这个值时,更新答案.

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
int n,m,a[1001],b[1001],f[1001],ans=0;
int main()
{
scanf("%d",&n);
fo(i,1,n)scanf("%d",&a[i]);
scanf("%d",&m);
fo(i,1,m)scanf("%d",&b[i]);
fo(i,1,n)
{
R int maxx=0;
fo(j,1,m)
{
if(a[i]>b[j])maxx=max(maxx,f[j]);
if(a[i]==b[j])f[j]=maxx+1;
}
}
fo(i,1,max(n,m))ans=max(ans,f[i]);
cout<<ans;
return 0;
}
显示 Gitment 评论