50pts求调（玄关）

fsc0190 @ 2024-04-30 14:48:23

#include<bits/stdc++.h>
using namespace std;
int n,a[10001],k[10001],f[10001][10001]; 
int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin >> k[i];
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (a[i] == k[j])
            {
                f[i][j] = max(f[i][j],f[i-1][j-1]+1);
            }
            else
            {
                f[i][j] = max(f[i-1][j],f[i][j-1]);
            }
        }
    }
    cout << f[n][n];
    return 0;
}

by wsr_jason @ 2024-04-30 14:53:17

@fsc0190 这道题得用 O(nlog_n) 的复杂度，你的复杂度是 O(n^2) ，所以会有点过不了。正解请看题解。

对于 100\% 的数据 , 保证 n \le 10^5

by fsc0190 @ 2024-04-30 14:54:37

@wsr_jason O(nlog n ​ ) 复杂度怎么写

by wsr_jason @ 2024-04-30 14:57:48

@fsc0190 用离散化和二分

by wsr_jason @ 2024-04-30 14:58:48

当然，单调栈也可以(虽然有一点难)

by __wjy__ @ 2024-04-30 20:03:07

用KMP?

by ylch @ 2024-05-01 21:55:22

dp求最长公共子序列复杂度是O(n^2)的话是会超时的，但是发现输入的数组是一个“排列”，即数字不重复，这成为了我们的破局之法。

最长公共子序列的长度=就是满足数字相同，且数字之间的相对顺序也相同的数字的个数。

考虑到不重复，可以用哈希，预处理出b数组中每个数在a数组中的下标数组c，求c的最长上升子序列长度即可。

因为已经哈希过了，同时数字不重复，不用考虑数字是否相同，只要考虑相对位置即可。相对位置升序的位置个数就是答案（就是求最长上升子序列长度）.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector <int> a(n + 1), b(n + 1), c(n + 1);
    unordered_map <int, int> vis;

    for(int i = 1; i <= n; i ++) cin >> a[i], vis[a[i]] = i;
    for(int i = 1; i <= n; i ++) cin >> b[i], c[i] = vis[b[i]];

    // 求c的最长上升子序列长度
    int pos = 0;
    vector <int> dp(n + 1);
    for(int i = 1; i <= n; i ++){
        if(i == 1 || c[i] > dp[pos]) dp[++ pos] = c[i]; // 如果大于的话，可以直接接到后面
        else{ // 否则寻找一个合适的插入位置
            int l = 1, r = pos, ans = -1;
            while(l <= r){ // 二分第一个大于等于c[i]的位置
                int mid = (l + r) >> 1;
                if(dp[mid] >= c[i]){
                    ans = mid;
                    r = mid - 1; // 继续往左走
                }else l = mid + 1;
            }
            dp[ans] = c[i];
        }
    }
    cout << pos << endl;
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

by ylch @ 2024-05-01 22:00:31

最长上升子序列教学