求助，悬赏一关！！！

P1439 【模板】最长公共子序列

zxbsdkk9468 @ 2024-04-02 16:26:19

4个点tle了不知道怎么优化，求解```c

include<iostream>

include<algorithm>

include<vector>

using namespace std; const int N = 101000; int a[N], b[N]; int f[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++)cin >> b[i]; for(int i=1;i<=n;i++) for (int j = 1; j <= n; j++) { f[j] = max(f[j], f[j - 1]); if (a[i] == b[j])f[j] = max(f[j], f[j - 1] + 1); } cout << f[n]; return 0; }

by zxbsdkk9468 @ 2024-04-02 16:27:11

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 101000;
int a[N], b[N];
int f[N];
int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)cin >> b[i];
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= n; j++)
        {
            f[j] = max(f[j], f[j - 1]);
            if (a[i] == b[j])f[j] = max(f[j], f[j - 1] + 1);
        }
    cout << f[n];
    return 0;
}

by lcezshiyuang @ 2024-04-06 11:33:22

这是ｎ平方的时间复杂度，数据范围1e5不可能不TLE的，快去题解区学习nlogn时间复杂度的算法吧

|