站外题目求助
  • 板块学术版
  • 楼主__Luna__
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/24 22:46
  • 上次更新2023/10/23 23:54:21
查看原帖
站外题目求助
901195
__Luna__楼主2023/2/24 22:46

题目:

最长公共子上升序列

描述

给定两个整数序列,写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列:

存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。

输入

每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )

输出

在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。

样例输入

5
1 4 2 5 -12
4
-12 1 2 4

样例输出

2
1 4

提交代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include <string>
using namespace std;
int main()
{
    int a[2][501],m1,m2,f[2][501];
    string g[2][501];
    cin >> m1;
    for (int i = 1; i <= m1; i++)
        cin >> a[0][i];
    cin >> m2;
    for (int i = 1; i <= m2; i++)
        cin >> a[1][i];
    for (int i = 1; i <= m1; i++)
    {
        int _max_ = 0;
        string __max__;
        for (int j = 1; j <= m2; j++)
        {
            f[1][j] = f[0][j];
            g[1][j] = g[0][j];
            if (a[0][i] > a[1][j])
            {
                if (_max_<f[0][j])
                {
                    _max_ = f[0][j];
                    __max__ = g[0][j];
                }
            }
            if (a[0][i] == a[1][j])
            {
                f[1][j] = _max_ + 1;
                g[1][j] = __max__ + " "+to_string(a[0][i]);
            }
        }
        for (int j = 1; j <= m2; j++)
        {
            f[0][j] = f[1][j];
            g[0][j] = g[1][j];
        }
    }
    int len = 0;
    string max_;
    for (int i = 1; i <= m2; i++) 
    {
        if (len < f[1][i])
        {
            len = f[1][i];
            max_ = g[1][i];
        }
    }
    cout << len << endl;
    cout << max_.substr(1, max_.size() - 1) << endl;
    return 0;
}

目前的问题是,有某一个测试点报错Runtime Error。题目所在的网站无法查看测试点,因此查不出报错的原因。
请大神赐教。

2023/2/24 22:46
加载中...