UVA 10635 Prince and Princess

UVA 10635 Prince and Princess

題目概述:

給兩個長度為p,q數字不重複的A,B兩個數列，求LCS。

思路:

這題如果直接做O(n2)的LCS很明顯得會TLE(p,q≦250*250)，那這題有個關鍵是這兩個數列的數字是不會重複的!

我的作法是我重新定義數字間的大小關係，然後對數列作LIS就是答案了!!

以範例作為例子

A={1,7,5,4,8,3,9};

B={1,4,3,5,6,2,8,9};

那我將本來的數字系統的數值關係(1<2<3<4<5.....)改為我自己定義的(Ai<Ai+1<Ai+2…<Ap-1<Ap)

所以數字關係會變成(1<7<5<4<8<3<9)。

接著再利用這個數字關係做LIS就是答案了!

那它的正確性要如何證明呢?

.

.

好吧我沒想到怎麼證明QQ

就先待補吧XD

AC code:

//By SCJ

//uva 10635

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define INF 100000000

int dp[251*251],mp[251*251];

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int T;cin>>T;

   for(int ca=1;ca<=T;++ca)

   {

       int n,p,q;cin>>n>>p>>q;

       memset(mp,-1,sizeof(mp));

       for(int i=0;i<=p;++i)

       {

           int tp;cin>>tp;

           mp[tp]=i;

       }

       for(int i=0;i<=n*n;++i) dp[i]=INF;

       for(int i=0;i<=q;++i)

       {

           int tp;cin>>tp;

           if(mp[tp]==-1) continue;

           *lower_bound(dp,dp+n*n,mp[tp])=mp[tp];

       }

       cout<<"Case "<<ca<<": "<<lower_bound(dp,dp+n*n,INF)-dp<<endl;

   }

}