50分蒟蒻求助!

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

yanbinmu @ 2022-07-16 08:50:01

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long  f[10005][10005];
int x[10005],y[10005]; 
int n;
int main()
{   
    cin>>n;
    for(int i = 1 ;i <= n;i++){
        cin>>x[i];
    }
    for(int i = 1 ;i <= n;i++){
        cin>>y[i];
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(x[i] == y[j]){
                f[i][j] = max(max(f[i-1][j],f[i][j-1]),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 Azure__ @ 2022-07-16 08:57:07

dp是过不了的,请自行学习O(n log n)的二分算法


by yanbinmu @ 2022-07-16 09:03:04

@Azure__ 谢谢


by MSqwq @ 2022-07-16 09:23:56


|