4个点TLE,求助神犇

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

135791a @ 2024-07-14 11:31:24

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

by chenlh0711 @ 2024-07-14 11:45:14

@135791a 这样直接dp肯定会T到起飞,这个题要用二分


by 135791a @ 2024-07-15 08:48:35

谢谢,神犇。@chenlh0711


|