UVA - 10635 Prince and Princess LCS转LIS

题目链接：

http://bak.vjudge.net/problem/UVA-10635

Prince and Princess

Time Limit: 3000MS

题意

题解

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

#include<sstream>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=255*255;

int mp[maxn];

int a[maxn],b[maxn];

int arr[maxn];

int main() {

    int tc,kase=0;

    int n,p,q;

    scf("%d",&tc);

    while(tc--){

        scf("%d%d%d",&n,&p,&q);

        p++,q++;

        clr(mp,-1);

        for(int i=1;i<=p;i++) scf("%d",&a[i]);

        for(int i=1;i<=q;i++){

            scf("%d",&b[i]);

            mp[b[i]]=i;

        }

        int tot=0;

        for(int i=1;i<=p;i++){

            if(mp[a[i]]>=0){

                arr[++tot]=mp[a[i]];

            }

        }

//        for(int i=1;i<=tot;i++) prf("%d\n",arr[i]);

        vector<int> ra;

        for(int i=1;i<=tot;i++){

            int pos=upper_bound(all(ra),arr[i])-ra.begin();

            if(pos==ra.sz()){

                ra.pb(arr[i]);

            }else{

                ra[pos]=arr[i];

            }

        }

        prf("Case %d: %d\n",++kase,ra.sz());

    }

    return 0;

}

//end-----------------------------------------------------------------------