题目

这题如果用\(f_{i,j}\)这样dp的话肯定过不了，必须另辟蹊径。题目说了数字不重复。我们先只留下两个数组共有的数字。然后我们处理出这样一个数组\(S\)，\(S_i\)表示\(A_i\)这个元素在\(B\)中的下标，然后模型转换就成为了求\(S\)中最长上升子序列了，这个\(O(NlogN)\)的求法大家应该都会。这里我写的是树状数组版本的。

#include
    
     #include
     
      #include
      
       using namespace std;#define lowbit(x) (x&-x)const int maxn = 250*250+10;int pos[maxn],S[maxn],T,tree[maxn],N,P,Q,cnt,ans;inline void ins(int a,int b) { for (;a <= N*N;a += lowbit(a)) tree[a] = max(tree[a],b); }inline int calc(int a) { int ret = 0; for (;a;a -= lowbit(a)) ret = max(ret,tree[a]); return ret; }inline int read(){    int ret = 0,f = 1; char ch;    do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');    if (ch == '-') ch = getchar(),f = -1;    do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');    return ret*f;}int main(){    freopen("10635.in","r",stdin);    freopen("10635.out","w",stdout);    scanf("%d",&T);    for (int Case = 1;Case <= T;++Case)    {        printf("Case %d: ",Case);        N = read(); P = read()+1; Q = read()+1; cnt = ans = 0;        for (int i = 1;i <= N*N;++i) pos[i] = tree[i] = 0;        for (int i = 1;i <= P;++i) pos[read()] = i;        for (int i = 1,b;i <= Q;++i)        {            b = read();             if (pos[b]) S[++cnt] = pos[b];        }        for (int i = 1;i <= cnt;++i)        {            int f = calc(S[i]-1)+1;            ans = max(ans,f); ins(S[i],f);        }        printf("%d\n",ans);    }    fclose(stdin); fclose(stdout);    return 0;}