HDU 5904 LCIS __ dp、LCIS

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
 
int dpa[maxn], dpb[maxn], a[maxn], b[maxn];
//map<int, vector<int> > Inda, Indb;
map<int, int> Inda, Indb;                 //维护最后一个ai的下标
 
 
int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
 
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
 
    int T, n, m, ans;
    cin >> T;
    while(T--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            //Inda[a[i]].push_back(i);
        }
        for(int i = 1; i <= m; i++){
            cin >> b[i];
            //Indb[b[i]].push_back(i);
        }
 
        int sz;
        for(int i = 1; i <= n; i++){
            if(i != 1){
                dpa[i] = dpa[Inda[a[i] - 1]] + 1;
                dpa[i] = max(dpa[i], dpa[Inda[a[i]]]);
            }
            else dpa[i] = 1;
            Inda[a[i]] = i;
        }
 
        for(int i = 1; i <= m; i++){
            if(i != 1){
                dpb[i] = dpb[Indb[b[i] - 1]] + 1;
                dpb[i] = max(dpb[i], dpb[Indb[b[i]]]);
            }
            else dpb[i] = 1;
            Indb[b[i]] = i;
        }
 
        ans = 0;
        for(int i = n; i > 0; i--){
            if(Indb[a[i]] != 0){
                ans = max(ans, min(dpa[i], dpb[Indb[a[i]]]));
            }
        }
 
        cout << ans << endl;
        Inda.clear(); Indb.clear();
 
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx