求最长不下降序列并输出序列（动态规划）

向右看齐 2022-06-08 07:12 142阅读 0赞

### 【例9.3】求最长不下降序列 ###

时间限制: 1000 ms 内存限制: 65536 KB

### 【题目描述】 ###

设有由n(1<=n<=200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j)(i<>j)，若存在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

### 【来源】 ###

[No][]

![20170918205131965][]

/*
    14
    13 7 9 16 38 24 37 18 44 19 21 22 63 15
    */
    #include<iostream>
    #include<cstring>
    #define MAXN 200
    using namespace std;
    int f[MAXN+10];//f[i]表示前i个数的最长不下降序列长度 
    int a[MAXN+10];//存储每个数的值 
    int pre[MAXN+10];//pre[i]表示从i开始最长不下降序列的前一个位置 
    int ans[MAXN+10];//存储最长不下降序列 
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(f,0,sizeof(f));
    	memset(pre,0,sizeof(pre));
    	int n,i,j,l,k;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		f[i]=1;//初始状态 
    	}
    	for(i=2;i<=n;i++)
    	{
    		l=0,k=0;
    		for(j=1;j<i;j++)
    		{
    			if((a[i]>=a[j])&&f[j]>l)//注意：一定要a[i]>=a[j]要加等号，否则数据通不过。如果是不上升序列，则a[i]<=a[j]
    			{
    				 l=f[j];
    				 k=j;
    			}
    		}
    		if(l>0)
    		{
    			f[i]=l+1;
    			pre[i]=k;
    		}	 
    	}
    	k=1;
    	for(int i=1;i<=n;i++)//从f[1]到f[n]中找到最大值 
    	{
    		if(f[i]>f[k]) k=i;		 
    	}
    	cout<<"max="<<f[k]<<endl;
    	int d=1;
    	while(k!=0)
    	{
    		ans[d++]=a[k];
    		k=pre[k];
    	}
    	for(i=d-1;i>=1;i--) cout<<ans[i]<<" ";//n逆序输出 
    	cout<<endl;
    	return 0;
    }

下面这样做数据只能对60%：

#include<iostream>
    #include<cstring>
    #define MAXN 200
    using namespace std;
    int f[MAXN+10];
    int a[MAXN+10];
    int pre[MAXN+10];
    int ans[MAXN+10];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(f,0,sizeof(f));
    	memset(pre,0,sizeof(pre));
    	int n,i,j;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		f[i]=1;
    	}
    	for(i=2;i<=n;i++)
    	{
    		for(j=1;j<i;j++)
    		{
    			if(a[i]>=a[j])
    			{
    				f[i]=max(f[i],f[j]+1);
    				pre[i]=j;
    			}
    		}
    	}
    	int k=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(f[i]>f[k]) k=i;
    	}
    	cout<<"max="<<f[k]<<endl;
    	int maxn=f[k],d=1;
    	while(maxn--)
    	{
    		ans[d++]=a[k];
    		k=pre[k];
    	}
    	for(i=d-1;i>=1;i--) cout<<ans[i]<<" ";
    	cout<<endl;
    	return 0;
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No
[20170918205131965]: /images/20220608/e267a3c2772740908bf90c4fdb334470.png