uva 10635 Prince and Princess（dp）

這個題目顯然用n^2的最長公共子序列的算法會逾時，後來看了别人的解題報告發現，原來最長公共子序列可以轉化成最長上升子序列的問題，然後用最長上升子序列的nlogn的算法求解。

lower_bound應該是用的二分查找，傳回第一個比s[i]大的

ac代碼

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int INF=100000000;
const int maxn=62600;
int s[maxn],num[maxn],g[maxn];
int main (){
  int t,cnt=0;
  scanf("%d",&t);
  while(t--)
  {
      int n,p,q,x;
      scanf("%d%d%d",&n,&p,&q);
      for(int i=1;i<=p+1;i++)scanf("%d",&x),num[x]=i;
    int N=0;
      for(int i=1;i<=q+1;i++)
      {scanf("%d",&x);
      if(num[x])s[N++]=num[x];
      }

     for(int i=1;i<=N;i++)g[i]=INF;
     int ans=0;
     for(int i=0;i<N;i++)
     {
         int k=lower_bound(g+1,g+N+1,s[i])-g;
         g[k]=s[i];
         ans=max(ans,k);
     }
     printf("Case %d: %d\n",++cnt,ans);
  }
    return 0;
}