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;
}