样例过了，没分(求助)

QirErl @ 2024-12-10 18:51:17

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

by xiezt123456 @ 2024-12-10 19:02:02

@QirErl思路就错了，子序列顺序不一定规律

by QirErl @ 2024-12-10 19:22:55

@xiezt123456所以我用了二维dp四重循环啊

by xiezt123456 @ 2024-12-10 19:28:10

@QirErl会MLE

记录

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[100001], b[100001];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    // 创建并初始化 dp 数组
    int dp[10001][10001];

    // 填充 dp 数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            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]);
            }
        }
    }

    // 输出结果
    cout << dp[n][n] << endl;

    return 0;
}