uva10635Prince and Princess

题意：有两个长度分别为p+1和q+1的序列，每个序列中的各个元素互不相同，且都是1~n²之间的整数，两个序列的第一个元素都是1，问A和B的最长公共子序列的长度

分析：由于在同一个序列中元素互不相同，可以转化LCS问题为LIS问题，使用了“置换的思想”，有点类似于“离散化”，然后用stl的lower_bound函数实现log级别的查找，使得整个复杂度为nlogn

代码：

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 using namespace std;
 6 #define DEBUG
 7 const int MAXN = 250 * 250;
 8 const int INF = 0x3f3f3f3f;
 9 int sun[MAXN];
10 int s[MAXN];
11 int g[MAXN];
12 int main(){
13 #ifndef DEBUG
14     freopen("in.txt", "r", stdin);
15 #endif
16     int T, cas=1;
17     scanf("%d", &T);
18     while(T--){
19         int N, p, q, x, i;
20         memset(sun, 0, sizeof(sun));
21         scanf("%d%d%d", &N, &p, &q);        //N is useless
22         for(i=1; i<=p+1; i++) {
23             scanf("%d", &x);
24             sun[x]=i;
25         }
26         int n = 0;
27         for(i=1; i<=q+1; i++){
28             scanf("%d", &x);
29             if(sun[x]) s[n++]=sun[x];
30         }
31         for(i=1; i<=n; i++) g[i]=INF;
32         int ans=0;
33         for(i=0; i<n; i++){
34             int k=lower_bound(g+1, g+n+1, s[i])-g;
35             g[k]=s[i];
36             if(ans<k) ans=k;
37         }
38         printf("Case %d: %d\n", cas++, ans);
39     }
40     return 0;
41 }

发现如果把数组名字设定为index则会报CE的错误，说是index是一个函数，⊙﹏⊙b汗

Greatness is never a given, it must be earned.