鱼C论坛

 找回密码
 立即注册
查看: 1955|回复: 1

c++最长子序列问题,有一个测试点不通过(不能看数据)

[复制链接]
发表于 2020-4-23 18:35:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
能请大佬帮忙看一下吗,要是实在嫌麻烦就别强求了

【题目描述】
设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)若存在i1<i2<i3<…<ie 且有b(i1)≤b(i2)≤…≤b(ie)则称为长度为e的不下降序列。程序要求,当原数列出之后,求出最长的不下降序列。

例如13,7,9,16,38,24,37,18,44,19,21,22,63,15。例中13,16,18,19,21,22,63就是一个长度为7的不下降序列,同时也有7 ,9,16,18,19,21,22,63组成的长度为8的不下降序列。

【输入】
第一行为n,第二行为用空格隔开的n个整数。

【输出】
第一行为输出最大个数max(形式见样例);

第二行为max个整数形成的不下降序列,答案可能不唯一,输出一种就可以了,本题进行特殊评测。

【输入样例】
14
13 7 9 16 38 24 37 18 44 19 21 22 63 15
【输出样例】
max=8
7 9 16 18 19 21 22 63
#include <iostream>

int a[205][3];
//0输入的数值
//1从开头到该位置的最长不下降序列长度
//2最长序列中上一个元素的位置,若为负数表示这个元素之前没有符合条件的位置

void print(int pos)//顺序输出序列的函数
{
    if(pos<0)
        return ;
    print(a[pos][2]);
    std::cout << a[pos][0] << " ";
}

int main()
{
    int n,tmp=0;
    std::cin >> n;
    for(int i=0; i<n; i++)
    {
        std::cin >> a[i][0];
        a[i][1]=1;
        a[i][2]=-1;
    }

    for(int i=0; i<n; i++)
        for(int j=i; j>=0; j--)
            if(a[j][0]<a[i][0])
                if(a[i][1]<a[j][1]+1)
                {
                    a[i][1]=a[j][1]+1;
                    a[i][2]=j;
                }

    for(int i=0; i<n; i++)
        if(a[i][1]>a[tmp][1])
            tmp=i;
    std::cout << "max=" << a[tmp][1] << std::endl;
    print(tmp);
    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-4-23 18:36:43 | 显示全部楼层
标题写错了,是最长不下降序列问题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-14 18:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表