关于最长不下降子序列
  • 板块题目总版
  • 楼主Carrot_Rui
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/13 16:38
  • 上次更新2023/11/5 08:10:16
查看原帖
关于最长不下降子序列
376481
Carrot_Rui楼主2020/11/13 16:38

QAQ我求出了最长不下降子序列的长度,但是我忽然发现我不知道该怎么数出子序列的数qaq

题目:

(该题不是洛谷的,因为我在洛谷上面找不到模板)

题目描述】

设有由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>
#include<cstdio> 
#define MAXN 5001
using namespace std;

int n,a[MAXN],f[MAXN],qaq[MAXN],num[MAXN],ans;

int max(int a,int b){
	return a>b?a:b;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]),f[i]=1;//初始长度为 1 
	}
	
	//从后面往前遍历 
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[i]>=a[j]&&f[j]+1>f[i])
			    f[i]=f[j]+1;
	
	  for(int i=1;i<=n;i++){
	  	ans=max(ans,f[i]);
		 // if(f[i]>ans) ans=f[i];
	  }
			printf("max=%d\n",ans);
			
		int p=0;
		// 取最大子序列的数到另外数组p充当新数组下标 
		for(int i=1;i<=n;i++){
			
		}
		
			for(int i=t;i>=1;i--)//输出子序列的数 
				printf("%d ",&qaq[i]);
			
	return 0;
}
2020/11/13 16:38
加载中...