// uva10635 Prince and Princess LCS 变 lIS// 本意求LCS，但是规模有60000多，复杂度肯定不够// 注意如果俩个序列的值的范围相同，那么可以在一个// 串中记录在另外一个串中的位置。这样就可以转化成// 最长上升子序列的问题啦，复杂度是nlogn，可以ac// 这题，还是挺有考究的价值的，很不错// 哎，，继续练吧。。。。。#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }template<class T> inline T lowBit(const T& x) { return x&-x; }template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 352 * 352;int a[maxn];int b[maxn];int n,p,q;int cnt;int dp[maxn];const int inf = 0x3f3f3f3f;void print(int a[],int p){for (int i=1;i<=p;i++)printf("%d ",a[i]);puts("");}void init(){scanf("%d%d%d",&n,&p,&q);memset(dp,inf,sizeof(dp));memset(b,0,sizeof(b));scanf("%d",&a[0]);int x;for (int i=1;i<=p;i++){scanf("%d",&x);a[x] = i;}scanf("%d",&b[0]);for (int i=1;i<=q;i++){scanf("%d",&x);b[i] = a[x];}//print(a,p);//print(b,q);cnt = 0;for (int i=1;i<=q;i++){if (b[i]){a[cnt++] = b[i];}}//print(a,p);}void solve(){for (int i=0;i<cnt;i++){*lower_bound(dp,dp+cnt,a[i]) = a[i];}int k = lower_bound(dp,dp+cnt,inf) – dp;printf("%d\n",k+1);}int main() {int t;//freopen("G:\\Code\\1.txt","r",stdin);scanf("%d",&t);int kase = 1;while(t–){init();printf("Case %d: ",kase++);solve();}return 0;}
把自己当傻瓜，不懂就问，你会学的更多
