TLE,怎么添加二分,求大佬帮助

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

ttltony @ 2023-01-31 15:07:31

#include <iostream>
#include <algorithm>

using namespace std;

int n, ans;
int a[10001], b[10001], dp[10001][10001];

int main() {
    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 ++ ) {
            if (dp[i][j]) continue;
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) ans = max(ans, dp[i][j]);
    cout << ans << endl;
    return 0;
}

代码如上,求问


by DreamLand_zcb @ 2023-01-31 15:12:37

@ttltony LIS的二分优化好像和你dp思路不一样

    g[0]=-INF;
    for(int i=1;i<=n;i++)   g[i]=INF;
    for(int i=1;i<=n;i++)
    {
        f[i]=upper_bound(g, g+n+1, a[i])-g;
        g[f[i]]=a[i];
        ans=max(ans, f[i]);
    }

by DreamLand_zcb @ 2023-01-31 15:18:41

@ttltony 开个桶表示p1[i]在p2中第一次出现的下标,然后再用LIS和二分优化


by ttltony @ 2023-01-31 15:47:04

@DreamLand_zcb 谢谢大佬QWQ


|