【题目描述】
设有由 n( 1≤n≤200)n(1≤n≤200)个不相同的整数组成的数列,记为: b( 1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)且 b( i)≠b(j)(i≠j)b(i)≠b(j)(i≠j),若存在 i 1<i2<i3<…<iei1<i2<i3<…<ie 且有 b( i1)<b(i2)<…<b(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
【来源】
No
题目解析:
按照动态规划原理,对输入数组a从前往后搜索(其实该从后往前,但都一样)
1. 对于a【1】,作为第一个数,从a【1】开始查找,只存在长度为1的不下降序列。可以找到定义一个数组b[1]=1;
2. 从a【2】开始查找,则存在下面两种可能性
若a【2】>a[1],则存在长度为2 的不下降子序列。b[1]=1,b[2]=2;
若a【2】<a[1], 则存在长度为1的不下降子序列。b[1]=1,b[2]=1;
3. 在b[1]b[2]…….b[i-1],找出一个比b[i]小的的且最长不下降子序列,作为它的后继续;
数组b记录从i位置到n的最长不下降序列长度,
数组c表示从i位置开始最长不下降序列的下一个位置,若c[i]==0,则表示后面没有链接项。
a[] |
13 |
7 |
9 |
16 |
38 |
24 |
37 |
18 |
44 |
19 |
21 |
22 |
63 |
15 |
|
| b[] |
1 |
1 |
2 |
3 |
4 |
4 |
5 |
4 |
6 |
5 |
6 |
7 |
8 |
3 |
|
| C[] |
0 |
0 |
2 |
3 |
4 |
4 |
6 |
4 |
7 |
8 |
10 |
11 |
12 |
3 |
|
代码实现:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn],i,j,k,maxx,c[maxn],num[maxn],b[maxn];//数组b记录从i位置到n的最长不下降序列长度,//数组c表示从i位置开始最长不下降序列的下一个位置,若c[i]==0,则表示后面没有链接项。
int main()
{int n;cin>>n;for(i=1;i<=n;i++){cin>>a[i]; //输入数组,并将b和c初始化b[i]=1;c[i]=0;}for(i=1;i<=n;i++) //求最长不下降序列{maxx=0;k=0;for(j=1;j<=i-1;j++)if(a[j]<=a[i]&&b[j]>maxx){maxx=b[j];k=j;}if(maxx>0){b[i]=maxx+1;c[i]=k;}}k=1;for(j=1;j<=n;j++) //求最长不下降序列最后位置if(b[j]>b[k]) k=j;cout<<"max="<<b[k]<<endl;i=0;while(k!=0) //因为不是倒着搜索的,我只能将数组fu给另一个,然后倒着输出{num[i]=a[k];k=c[k];i++;}for(j=i-1;j>=0;j--)cout<<num[j]<<" ";return 0;
}