求调

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

hnoi @ 2023-03-19 12:19:31

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int dp[maxn],a[maxn],b[maxn],map1[maxn];
int ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        dp[i]=0;
    } 
    for(int i=1;i<=n;i++){
            cin>>a[i];
    }
    for(int i=1;i<=n;i++){
            cin>>b[i];
            map1[b[i]]=i;
    }
    for(int i=n;i>=1;i--){
        for(int j=n;j>i;j--){
            if(map1[j]>map1[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dp[i]>ans) ans=dp[i];
        cout<<dp[i]<<" "; 
    }
    cout<<endl;
    cout<<ans;
}

我用map数组存储b[i]在a数组中的位置 map数组的最长上升子序列即为a,b数组的最长公共子序列 但是样例每次都多1 不知道哪里写错了 求调整

by hnoi @ 2023-03-23 22:13:35

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int dp[maxn],a[maxn],b[maxn],map1[maxn];//map1数组存储b中元素在a中的位置 
int ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) dp[i]=1; 
    for(int i=1;i<=n;i++){
            cin>>a[i];
            map1[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
            cin>>b[i];
        }
    for(int i=n;i>=1;i--){
        for(int j=n;j>i;j--){
            if(map1[j]>map1[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dp[i]>ans) ans=dp[i];
    }
    cout<<ans;
}

又调整了一下 结果还是wa加re 求大佬解答

by _wakeup @ 2023-05-05 13:07:35

@CHYYDS 最大数据是10^5，你只开1e3肯定会RE啊

by _wakeup @ 2023-05-05 13:08:42

(但是你好像已经过了，溜了溜了

|