2016 UESTC Training for Dynamic Programming H – 柱爷大战滑稽王 LCS转LIS

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
const int maxn = 1e6 + 8;
map<int, int> m;
int li[maxn], t[maxn], liagain[maxn];
int len;


//!LCS 转 LIS O(m*n) ==> O(nlogn)
//!注意可能两个串一个公共的都没有，用ptr，是否被递增过来算
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int N, M, val;
    int ptr;
    scanf("%d%d", &N, &M);


        for(int i = 1; i <= N; i++){
            scanf("%d", &val);
            m[val] = i;
        }
        ptr = 0;
        for(int i = 1; i <= M; i++){
            scanf("%d", &val);
            if(m[val] > 0){
                li[ptr] = m[val];
                ptr++;
            }
        }




    //加了B可以重复的数据被cha了，这样只用A来映射好了，然后对原来的li[]再进行处理，如果没有映射值的就是0；
    int ptragain = 0;
    memset(liagain, 0, sizeof liagain);
    for(int i = 0; i < ptr; i++){
        if(li[i]!=0){
            liagain[ptragain] = li[i];
            ptragain++;
        }
    }
    memset(t, 0, sizeof t);
    len = t[0] = 0;
    int dp;
    for(int i = 0; i < ptragain; i++){
        dp = lower_bound(t, t+len+1, liagain[i])-t;
        len = max(len, dp);
        t[dp] = liagain[i];
    }
    /*
    t[1] = li[1];
    len=1;
    int p = ptr-1;
    for(int i=2; i <= p; i++){
        if(li[i]>t[len])
            t[++len] = li[i];
        else{
            int pos=lower_bound(t,t+len+1,li[i])-t;
            t[pos] = li[i];
}
    }
    */
    printf("%d",len+1);
    //else printf("1");                //这个时候没有数是一样的
    return 0;
}