UVA 10635 Prince and Princess 递推

uva的题就不粘题目了 传送门：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576

这道题先把第一组数据编上号，然后第二组数据对上第一组的号，在第一组没出现的就不用管了，因为第一个人跳不到那，然后求一下最长上升子序列，第一次我是用暴力搜的，居然1000ms+过了，但是时间太长不行啊，就改了二分，10msAC

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T,n,p,q,a[62505],b[62505],cur,ans,c[62505],temp;
    cin>>T;
    for(int k=1;k<=T;k++)
    {
        cin>>n>>p>>q;
        ans=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0x3f3f3f,sizeof(c));
        for(int i=1;i<=p+1;i++)
        {
            scanf("%d",&temp);
            a[temp]=i;
        }
        cur=1;
        for(int i=1;i<=q+1;i++)
        {
            scanf("%d",&temp);
            if(a[temp]!=0)
                b[cur++]=a[temp];
        }
        for(int i=1;i<cur;i++)
        {
            temp=lower_bound(c+1,c+cur,b[i])-c;
            c[temp]=b[i];
            ans=max(ans,temp);
        }
        cout<<"Case "<<k<<": "<<ans<<endl;
    }
    return 0;
}