UVa 10635 - Prince and Princess(LCS转LIS)

给出两个序列,第一个序列中的数不重复,求两个序列的LCS。
以为第一个序列的数不同,所以可以保存数在第一个序列中出现的顺序,然后删除第二个序列中不再第一个序列中的数,将剩下的数换成在第一个序列中出现的位置,对处理好的
序列求LIS。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=62510;
int s[maxn],num[maxn],d[maxn];
int main(){
int t,tt=0;scanf("%d",&t);
while(t--){
int n,p,q;
scanf("%d%d%d",&n,&p,&q);
memset(num,0,sizeof num);
for(int i=1;i<=p+1;++i){
int x;scanf("%d",&x);
num[x]=i;
}
n=0;
for(int i=0;i<=q;++i){
int x;scanf("%d",&x);
if(num[x]) s[n++]=num[x];
}
fill(d,d+n,inf);
for(int i=0;i<n;++i) *lower_bound(d,d+n,s[i])=s[i];
printf("Case %d: %d\n",++tt,int(lower_bound(d,d+n,inf)-d));
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包