信息学奥赛一本通1259：【例9.3】求最长不下降序列

题目： 

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

时间限制: 1000 ms         内存限制: 65536 KB
提交数:51218    通过数: 20928    Special Judge

【题目描述】

设有由n(1≤n≤200)n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)若存在i1<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就是一个长度为77的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为88的不下降序列。

【输入】

第一行为nn,第二行为用空格隔开的nn个整数。

【输出】

第一行为输出最大个数maxmax(形式见样例)；

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

【输入样例】

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

---

思路： 

首先这是动规题，所以定义一个dp，dp【i】表示数组的前 i 项的最长不下降序列的长度

显然，dp[1]=1

然后我们计算 dp[2] 到 dp[n] 的值（也就是放一个从2到n的循环）

我们想一下，dp[i]是和dp[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]相关的，如果我们在dp[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]中找到一个最大的数（假设最大的数是dp[4]）

如果a[4]<=a[i]，那么dp[i]=dp[4]+1

（为什么要+1呢？因为dp【i】是一个新的数字，所以加1）

这样我们就得出了dp[i]的计算方法：

当dp【x】是    dp【1】   到    dp【i-1】  这些数中最大的数，并且a【x】<=a【i】，那么dp【i】=dp【x】+1

---

代码： 

这是我写的，但3个样例错了

//我！的！代！码！，错！了！三！个！样！例！
//我！觉！得！是！输！出！不！下！降！序！列！的！时！候！出！问！题！了！
#include<bits/stdc++.h>
using namespace std;
long long a[210];
long long dp[210];
long long jl[210],ma=0,w;
struct aa{long long d[210],cd;
}s[210];
int main(){long long n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}dp[1]=1;//前1项的最长不下降子序列的长度为1 s[1].cd=1;s[1].d[1]=a[1];for(int i=2;i<=n;i++){long long ma=0;for(int j=1;j<=i;j++){//从1到i-1里面找答案 if(a[j]<=a[i]){//如果不下降 if(ma<dp[j]){//找个最大的数 ma=dp[j];//下一行不用看了，我输出序列的代码好像没写对 w=j; }}			}dp[i]=ma+1;//下面4行不用看了，我输出序列的代码好像没写对 s[i].cd=s[w].cd+1;for(int j=1;j<s[i].cd;j++){s[i].d[j]=s[w].d[j];}s[i].d[s[i].cd]=a[i];}long long zuid=0;//zuid的意思是dp[1]到dp[n]中最大的数字 for(int i=1;i<=n;i++){if(dp[i]>zuid){zuid=dp[i];//下一行不用看了，我输出序列的代码好像没写对 w=i;}}cout<<"max="<<zuid<<endl;//下面3行不用看了，我输出序列的代码好像没写对 for(int i=1;i<=s[w].cd;i++){cout<<s[w].d[i]<<" ";}return 0;
}

正确代码来自这篇文章：1259：【例9.3】求最长不下降序列_1259:【例9.3】求最长不下降序列-CSDN博客 

为什么我没有改代码，而是把别人的代码拿过来呢？因！为！我！不！想！改！了 ！

//这！个！代！码！才！是！对！的！
#include<bits/stdc++.h>
using namespace std;
int a[205],dp[205],pre[205];
void printff(int k){if(k == -1) return ;printff(pre[k]);cout<<a[k]<<' ';
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];dp[i] =1;pre[i] =-1;}int ans=-1,bk;for(int i=1;i<=n;i++){dp[i] =1;for(int j=1;j<i;j++){if(a[i] >= a[j] && dp[j] + 1 >dp[i]){dp[i] =dp[j] + 1;pre[i] = j;}}if(dp[i] > ans){ans=dp[i];bk=i;}}printf("max=%d\n",ans);printff(bk);return 0;
}