UVa10635 Prince and Princess（LCS）

題目連結

分析：

最長公共子序列

轉換成LIS的nlogn做法

tip

不要忘了using namespace std

外國的網站做的就是好，比某爆炸oj高到不知哪裡去了

然而就是在國内不翻牆的話挺慢的

題目比較難找，但是submit要友善得多

//這裡寫代碼片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n,p,q;
int g[],a[],num[];

int doit()
{
    int t=;
    g[]=a[];
    for (int i=;i<=n;i++)
    {
        if (a[i]>g[t]) g[++t]=a[i];
        int r=lower_bound(g+,g++t,a[i])-g;  //>=的第一個 
        g[r]=a[i];
    }
    return t;
}

int main()
{
    int TT;
    scanf("%d",&TT);
    for (int T=;T<=TT;T++)
    {
        scanf("%d%d%d",&n,&p,&q);
        for (int i=;i<=p+;i++)
        {
            int x;
            scanf("%d",&x);
            num[x]=i;   //x在a中的位置 
        }
        n=;
        for (int i=;i<=q+;i++)
        {
            int x;
            scanf("%d",&x);
            if (num[x])   //出現過 
                a[++n]=num[x];
        }
        printf("Case %d: %d\n",T,doit());
    }
    return ;
}