題目：?

1259：【例9.3】求最長(zhǎng)不下降序列

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù):51218??? 通過(guò)數(shù):?20928????Special Judge

【題目描述】

【輸入】

【輸出】

【輸入樣例】

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

---

思路：?

首先這是動(dòng)規(guī)題，所以定義一個(gè)dp，dp【i】表示數(shù)組的前 i 項(xiàng)的最長(zhǎng)不下降序列的長(zhǎng)度

顯然，dp[1]=1

然后我們計(jì)算 dp[2] 到 dp[n] 的值（也就是放一個(gè)從2到n的循環(huán)）

我們想一下，dp[i]是和dp[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]相關(guān)的，如果我們?cè)赿p[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]中找到一個(gè)最大的數(shù)（假設(shè)最大的數(shù)是dp[4]）

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

（為什么要+1呢？因?yàn)閐p【i】是一個(gè)新的數(shù)字，所以加1）

這樣我們就得出了dp[i]的計(jì)算方法：

當(dāng)dp【x】是? ? dp【1】? ?到? ? dp【i-1】? 這些數(shù)中最大的數(shù)，并且a【x】<=a【i】，那么dp【i】=dp【x】+1

---

代碼：?

這是我寫(xiě)的，但3個(gè)樣例錯(cuò)了

//我！的！代！碼！，錯(cuò)！了！三！個(gè)！樣！例！
//我！覺(jué)！得！是！輸！出！不！下！降！序！列！的！時(shí)！候！出！問(wèn)！題！了！
#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項(xiàng)的最長(zhǎng)不下降子序列的長(zhǎng)度為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]){//找個(gè)最大的數(shù) ma=dp[j];//下一行不用看了，我輸出序列的代碼好像沒(méi)寫(xiě)對(duì) w=j; }}			}dp[i]=ma+1;//下面4行不用看了，我輸出序列的代碼好像沒(méi)寫(xiě)對(duì) 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]中最大的數(shù)字 for(int i=1;i<=n;i++){if(dp[i]>zuid){zuid=dp[i];//下一行不用看了，我輸出序列的代碼好像沒(méi)寫(xiě)對(duì) w=i;}}cout<<"max="<<zuid<<endl;//下面3行不用看了，我輸出序列的代碼好像沒(méi)寫(xiě)對(duì) for(int i=1;i<=s[w].cd;i++){cout<<s[w].d[i]<<" ";}return 0;
}

正確代碼來(lái)自這篇文章：1259：【例9.3】求最長(zhǎng)不下降序列_1259:【例9.3】求最長(zhǎng)不下降序列-CSDN博客?

為什么我沒(méi)有改代碼，而是把別人的代碼拿過(guò)來(lái)呢？因！為！我！不！想！改！了 ！

//這！個(gè)！代！碼！才！是！對(duì)！的！
#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;
}