FASTergood @ 2024-04-28 20:49:03

#include<iostream>  
#include<algorithm>  
#include<map>  
#include<climits> 
using namespace std;

const int N = 1e5 + 3;

int a[N], b[N], ans;
char x[N], y[N];
int f[N]; 

int main()
{
    map<int, char> q;
    int m, i;
    cin >> m;

    for (i = 1; i <= m; i++)
    {
        cin >> a[i];
        q[a[i]] = 'a' + i - 1; 
        x[i] = q[a[i]];
    }

    fill_n(f, N, INT_MAX); 

    for (i = 1; i <= m; i++)
    {
        cin >> b[i];
        y[i] = q[b[i]];
    }

    ans = 0; 

    for (i = 1; i <= m; i++)
    {
        int l = 1, r = i;
        while (l < r)
        {
            int mid = l + (r - l) / 2;   
            if (y[i] < f[mid])
                r = mid;
            else
                l = mid + 1;
        }

        if (y[i] < f[l]) 
            f[l] = y[i];

        ans = max(ans, l); 
    }

    cout << ans << endl;

    return 0;
}

by FASTergood @ 2024-04-28 21:18:33

会了 来还愿

20pst原因：字符爆炸

ascii库里面没有超过1e5的数据 ，因此想要LIS必须“以数代数”

AC code

#include<iostream>  
#include<algorithm>  
#include<map>  
#include<climits> 
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], ans;
int x[N], y[N];
int f[N]; 
int main()
{
    map<int, int> q;
    int m, i;
    cin >> m;

    for (i = 1; i <= m; i++)
    {
        cin >> a[i];
        q[a[i]] = 1 + i - 1; //几乎只有这里改动了。
        x[i] = q[a[i]];
    }

    fill_n(f, N, INT_MAX); 

    for (i = 1; i <= m; i++)
    {
        cin >> b[i];
        y[i] = q[b[i]];
    }

    ans = 0; 

    for (i = 1; i <= m; i++)
    {
        int l = 1, r = i;
        while (l < r)
        {
            int mid = l + (r - l) / 2;   
            if (y[i] < f[mid])
                r = mid;
            else
                l = mid + 1;
        }

        if (y[i] < f[l]) 
            f[l] = y[i];

        ans = max(ans, l); 
    }

    cout << ans << endl;

    return 0;
}

by mooktian @ 2024-04-29 10:43:39

@FASTergood 大佬，为什么要手搓二分呢？用upper_bound不好么？？