動態(tài)規(guī)劃——最長上升子序列模型-創(chuàng)新互聯

最長上升子序列模型：

給定一個長度為?N?的數列，求數值嚴格單調遞增的子序列的長度最長是多少。

成都創(chuàng)新互聯公司專注于廣南網站建設服務及定制，我們擁有豐富的企業(yè)做網站經驗。熱誠為您提供廣南營銷型網站建設，廣南網站制作、廣南網頁設計、廣南網站官網定制、成都小程序開發(fā)服務，打造廣南網絡公司原創(chuàng)品牌,更為您提供廣南網站排名全網營銷落地服務。

輸入格式：

第一行包含整數?N。

第二行包含?N?個整數，表示完整序列。

輸出格式：

輸出一個整數，表示大長度。

例如：3 1 2 1 8 5 6這個序列的最長遞增子序列長度為4（1 2 5 6）。

思路：

f[i]表示以i為結尾的所有上升子序列中最長的那個序列的長度。狀態(tài)計算：f[i]=f[j]+1，f[j]為i前面的子序列中可以連接到i前面的最長的一個序列（也就是j

代碼如下：

#includeusing namespace std;
const int N = 1010;
int f[N], a[N];
int n, res = 1;

int main() {
    cin >>n;

    for (int i = 0; i< n; i++) {
        cin >>a[i];
        f[i] = 1;

        for (int j = 0; j< i; j++)
            if (a[j]< a[i]) {
                f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
    }

    cout<< res;
    return 0;
}

例題：

1.怪盜基德：

假設城市中一共有N幢建筑排成一條線，每幢建筑的高度各不相同。

初始時，怪盜基德可以在任何一幢建筑的頂端。

他可以選擇一個方向逃跑，但是不能中途改變方向。

因為滑翔翼動力裝置受損，他只能往下滑行（只能從較高的建筑滑翔到較低的建筑）。

他希望盡可能多地經過不同建筑的頂部。

請問，他最多可以經過多少幢不同建筑的頂部。

輸入格式：

輸入數據第一行是一個整數K，代表有K組測試數據。

每組測試數據包含兩行：第一行是一個整數N，代表有N幢建筑。第二行包含N個不同的整數，每一個對應一幢建筑的高度h，按照建筑的排列順序給出。

輸出格式：

對于每一組測試數據，輸出一行，包含一個整數，代表怪盜基德最多可以經過的建筑數量。

思路：

我們求出以每個點為結尾的最長上升子序列的長度，就是求出了以每個點為起點向左往下飛的最多建筑數量；

我們求出以每個點為結尾的最長下降子序列的長度，就是求出了以每個點為終點的往右飛的最多建筑數量。

所以我們求出兩者取大值即可。

代碼如下：

#includeusing namespace std;
const int N = 110;
int a[N], f_up[N], f_down[N];
int K, n;

int main() {
    cin >>K;

    while (K--) {
        cin >>n;
        int max_u = 1, max_d = 1;

        for (int i = 0; i< n; i++) {
            cin >>a[i];
            f_up[i] = f_down[i] = 1;

            for (int j = 0; j< i; j++) {
                if (a[j]< a[i]) { f_up[i] = max(f_up[i], f_up[j] + 1); max_u = max(max_u, f_up[i]); }
                else if (a[j] >a[i]) { f_down[i] = max(f_down[i], f_down[j] + 1); max_d = max(max_d, f_down[i]); }
            }

        }
        cout<< max(max_u, max_d)<< endl;
    }

    return 0;
}

2.登山：

山上一共有N個景點，每個景點有對應的編號。

隊員決定按照順序來瀏覽這些景點，即每次所瀏覽景點的編號都要大于前一個瀏覽景點的編號。

同時隊員們還有另一個登山習慣，就是不連續(xù)瀏覽海拔相同的兩個景點，并且一旦開始下山，就不再向上走了。

問最多能瀏覽多少個景點。

思路：

要求的是先上升再下降的最長子序列。

從前往后求一遍上升子序列；

從后往前求一遍上升子序列（相當于從前往后下降）。

然后找出哪個點的上升和下降子序列之和大，答案就是大值減一。

代碼如下：

#includeusing namespace std;

const int N = 1010;
int a[N], f_up[N], f_down[N];
int n, res = 1;

int main() {
    cin >>n;

    for (int i = 0; i< n; i++) {
        cin >>a[i];
        f_up[i] = 1;

        for (int j = 0; j< i; j++)
            if (a[j]< a[i])f_up[i] = max(f_up[i], f_up[j] + 1);

    }

    for (int i = n - 1; i >= 0; i--) {
        f_down[i] = 1;

        for (int j = n - 1; j >i; j--)
            if (a[j]< a[i])f_down[i] = max(f_down[i], f_down[j] + 1);

        res = max(res, f_down[i] + f_up[i]);
    }

    cout<< res - 1;

    return 0;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：動態(tài)規(guī)劃——最長上升子序列模型-創(chuàng)新互聯
文章出自：http://muchs.cn/article22/dchpcc.html

成都網站建設公司_創(chuàng)新互聯，為您提供關鍵詞優(yōu)化、網頁設計公司、網站維護、網站改版、虛擬主機、云服務器

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯

猜你還喜歡下面的內容