題目描述

思路分析

• 目前是有一個(gè)笨辦法，就是創(chuàng)建鏈表記錄每一個(gè)最長下降子序列所對應(yīng)的節(jié)點(diǎn)的鏈接，然后逐個(gè)記錄所有結(jié)點(diǎn)的訪問情況，直接所有節(jié)點(diǎn)都被訪問過。
• 這個(gè)方法不是很好，因?yàn)樾枰?jì)算很多次，會(huì)超時(shí)，這里用了貪心的方法來證明，雖然不是最優(yōu)子序列，但是數(shù)量是一致的。

實(shí)現(xiàn)源碼

#include <iostream>
#include <algorithm>
#include <sstream>using namespace std;const int K = 110;
const int N = 110;
const int H = 12000;
int h[H];
int Up[N];
int Down[N];
struct Node {int idx;Node *next;
};
bool DownAcess[N];
Node DownRecord[N];  // 記錄下降節(jié)點(diǎn)的序列int main() {int n = 1;string line;getline(cin,line);stringstream ss(line);while(ss>>h[n]) n++;n --;int times = 0;bool endFlag = true ;
//    while(endFlag){
//        endFlag = false;
//        times ++;
//        int maxIdx = 1;
//        int maxNum = 0;// 計(jì)算最長上升子序列int res = 0;for (int i = n; i >= 1; -- i) {Down[i] = 1;DownRecord[i].idx = i;// 右側(cè)最長上升子序列for (int k = n; k > i ; --k) {if (h[k] <= h[i]){Down[i] = max(Down[i], Down[k] + 1);if (Down[i] < Down[k] + 1)DownRecord[i].next = &DownRecord[k];}}res = max(res, Down[i]);}cout<<res<<endl;
//
//        for (int i = 1; i <= n; ++i) {
//            if (maxNum < Down[i]) {
//                maxIdx = i;
//            }
//        }
//
//        Node *temp = &DownRecord[maxIdx];
//        while(temp != NULL){
//            DownAcess[temp->idx]  = true;
//        }
//
//        for (int i = 1; i <= n; ++i) {
//            if (DownAcess[i] == false) endFlag = true;
//        }//    }
//    cout<<times<<endl;return 0;
}
//  正解
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 1005;
//int n;
//int q[N];
//int f[N],g[N]
//
//int main()
//{
//    while(cin>> q[n])  n ++;
//    int res = 0;
//    for (int i = 0; i < n; ++i) {
//        for (int j = 0; j < i; ++j) {
//            if (q[j] <= q[i])
//                f[i] = max(f[i],f[j] + 1);
//        }
//        res = max(res,f[i]);
//    }
//    cout<<res<<endl;
//
//    int cnt = 0;
//    for(int i = 0;i < n;i ++){
//        int k = 0;  // 維護(hù)的索引的序列
//        while(k < cnt && g[k] < q[i]) k ++;  // 遍歷的每一個(gè)維護(hù)的最大的序列值
//        g[k] = q[i];
//        if(k >= cnt) cnt ++;
//
//    }
//}

分析總結(jié)

• 這里的證明看的不是很懂，但是用樣例推過了，確實(shí)是正確的。使用貪心求最少的子序列數(shù)量，和兩次最優(yōu)子序列是相同的。
• 但是如果確實(shí)想不起來，確實(shí)可以使用這個(gè)方法進(jìn)行實(shí)驗(yàn)。