[信息学奥赛一本通：1306最长公共子上升序列]第五个点WA了,悬赏一个关注!

Question

1306：最长公共子上升序列

90pts

第五个点WA了

Code:

#include<cstdio>
#include<algorithm>
using namespace std;

#define int long long
#define N 505
#define prev prevs 

int n,m;
int a[N],b[N];
int dp[N][N];
int prev[N];

void print(int ans)
{
    if(prev[ans])
        print(prev[ans]);
    printf("%lld ",a[ans]);
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=1;i<=m;++i)
        scanf("%lld",&b[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(a[i]==b[j])
            {
                dp[i][j]=1;
                for(int t=1;t<i;++t)
                    if(a[t]<a[i])
                        if(dp[i][j]<dp[t][j-1]+1)
                        {
                            dp[i][j]=dp[t][j-1]+1;
                            prev[i]=t;
                        }
            }
            else dp[i][j]=dp[i][j-1];
    int ans=0,ansi=0;
    for(int i=1;i<=m;++i)
        if(ans<dp[i][m])
        {
            ans=dp[i][m];
            ansi=i;
        }
    printf("%lld\n",ans);
    if(ans)
        print(ansi);
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的C++代码中，存在一个逻辑错误，导致第五个测试点的结果不正确。问题出在计算最长公共子上升序列（LCS）时，当a[i] != b[j]时，更新dp[i][j]值的部分。这个部分应该基于当前元素与前一个元素的关系来更新，而不是仅依赖于前一行的值。

下面是修改后的代码，修复了这个问题：

#include <iostream>
#include <algorithm>
using namespace std;

#define int long long
#define N 505
#define prev prevs 

int n, m;
int a[N], b[N];
int dp[N][N];
int prev[N];

void print(int ans)
{
    if (prev[ans]) {
        print(prev[ans]);
    }
    cout << a[ans] << " ";
}

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

    // 初始化第一行和第一列
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = 0;
    }
    for (int j = 1; j <= m; ++j) {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) {
                dp[i][j] = 1;
                for (int t = 1; t < i; ++t) {
                    if (a[t] < a[i]) {
                        if (dp[i][j] < dp[t][j - 1] + 1) {
                            dp[i][j] = dp[t][j - 1] + 1;
                            prev[i] = t;
                        }
                    }
                }
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i][j] == dp[i - 1][j]) { // 如果是来自上一列的最长序列
                    prev[i] = i - 1;
                } else { // 否则，是从左列来的最长序列
                    prev[i] = prev[j];
                }
            }
        }
    }

    int ans = dp[n][m];
    int ansi = n;
    while (ansi > 0 && dp[ansi][m] != ans) {
        ansi = prev[ansi];
    }
    
    cout << ans << endl;
    if (ans) {
        print(ansi);
    }

    return 0;
}

主要更改的地方是在处理a[i] != b[j]的情况时，修复了更新dp[i][j]的逻辑。现在，根据dp[i - 1][j]和dp[i][j - 1]中的较大值来更新dp[i][j]，并相应地更新prev[i]。这确保了我们在递归过程中考虑到正确的路径。此外，在输出最长公共子上升序列之前，我们先找到对应的索引ansi，使得dp[ansi][m]等于ans。这样可以保证输出的序列是正确的。