最長(zhǎng)上升子序列模型：

給定一個(gè)長(zhǎng)度為?N?的數(shù)列，求數(shù)值嚴(yán)格單調(diào)遞增的子序列的長(zhǎng)度最長(zhǎng)是多少。

成都創(chuàng)新互聯(lián)公司專(zhuān)注于廣南網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供廣南營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，廣南網(wǎng)站制作、廣南網(wǎng)頁(yè)設(shè)計(jì)、廣南網(wǎng)站官網(wǎng)定制、成都小程序開(kāi)發(fā)服務(wù)，打造廣南網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供廣南網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

輸入格式：

第一行包含整數(shù)?N。

第二行包含?N?個(gè)整數(shù)，表示完整序列。

輸出格式：

輸出一個(gè)整數(shù)，表示大長(zhǎng)度。

例如：3 1 2 1 8 5 6這個(gè)序列的最長(zhǎng)遞增子序列長(zhǎng)度為4（1 2 5 6）。

思路：

f[i]表示以i為結(jié)尾的所有上升子序列中最長(zhǎng)的那個(gè)序列的長(zhǎng)度。狀態(tài)計(jì)算：f[i]=f[j]+1，f[j]為i前面的子序列中可以連接到i前面的最長(zhǎng)的一個(gè)序列（也就是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.怪盜基德：

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

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

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

因?yàn)榛枰韯?dòng)力裝置受損，他只能往下滑行（只能從較高的建筑滑翔到較低的建筑）。

他希望盡可能多地經(jīng)過(guò)不同建筑的頂部。

請(qǐng)問(wèn)，他最多可以經(jīng)過(guò)多少幢不同建筑的頂部。

輸入格式：

輸入數(shù)據(jù)第一行是一個(gè)整數(shù)K，代表有K組測(cè)試數(shù)據(jù)。

每組測(cè)試數(shù)據(jù)包含兩行：第一行是一個(gè)整數(shù)N，代表有N幢建筑。第二行包含N個(gè)不同的整數(shù)，每一個(gè)對(duì)應(yīng)一幢建筑的高度h，按照建筑的排列順序給出。

輸出格式：

對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)，代表怪盜基德最多可以經(jīng)過(guò)的建筑數(shù)量。

思路：

我們求出以每個(gè)點(diǎn)為結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度，就是求出了以每個(gè)點(diǎn)為起點(diǎn)向左往下飛的最多建筑數(shù)量；

我們求出以每個(gè)點(diǎn)為結(jié)尾的最長(zhǎng)下降子序列的長(zhǎng)度，就是求出了以每個(gè)點(diǎn)為終點(diǎn)的往右飛的最多建筑數(shù)量。

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

代碼如下：

#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個(gè)景點(diǎn)，每個(gè)景點(diǎn)有對(duì)應(yīng)的編號(hào)。

隊(duì)員決定按照順序來(lái)瀏覽這些景點(diǎn)，即每次所瀏覽景點(diǎn)的編號(hào)都要大于前一個(gè)瀏覽景點(diǎn)的編號(hào)。

同時(shí)隊(duì)員們還有另一個(gè)登山習(xí)慣，就是不連續(xù)瀏覽海拔相同的兩個(gè)景點(diǎn)，并且一旦開(kāi)始下山，就不再向上走了。

問(wèn)最多能瀏覽多少個(gè)景點(diǎn)。

思路：

要求的是先上升再下降的最長(zhǎng)子序列。

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

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

然后找出哪個(gè)點(diǎn)的上升和下降子序列之和大，答案就是大值減一。

代碼如下：

#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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱(chēng)：動(dòng)態(tài)規(guī)劃——最長(zhǎng)上升子序列模型-創(chuàng)新互聯(lián)
文章出自：http://www.chinadenli.net/article22/dchpcc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站維護(hù)、網(wǎng)站改版、虛擬主機(jī)、云服務(wù)器

廣告

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