題目描述

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供競(jìng)秀網(wǎng)站建設(shè)、競(jìng)秀做網(wǎng)站、競(jìng)秀網(wǎng)站設(shè)計(jì)、競(jìng)秀網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、競(jìng)秀企業(yè)網(wǎng)站模板建站服務(wù)，10余年競(jìng)秀做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

五一到了，ACM隊(duì)組織大家去登山觀光，隊(duì)員們發(fā)現(xiàn)山上一共有N個(gè)景點(diǎn)，并且決定按照順序來(lái)瀏覽這些景點(diǎn)，即每次所瀏覽景點(diǎn)的編號(hào)都要大于前一個(gè)瀏覽景點(diǎn)的編號(hào)。
同時(shí)隊(duì)員們還有另一個(gè)登山習(xí)慣，就是不連續(xù)瀏覽海拔相同的兩個(gè)景點(diǎn)，并且一旦開(kāi)始下山，就不再向上走了。
隊(duì)員們希望在滿足上面條件的同時(shí)，盡可能多的瀏覽景點(diǎn)，你能幫他們找出最多可能瀏覽的景點(diǎn)數(shù)么？

思路

用兩個(gè)數(shù)組分別求從左邊的最長(zhǎng)上升和從右邊的最長(zhǎng)上升，最后再枚舉一邊就行了。

程序設(shè)計(jì) 代碼結(jié)構(gòu)：

導(dǎo)入萬(wàn)能頭文件“”#include“”并使用用標(biāo)準(zhǔn)命名空間。

定義三個(gè)int型的數(shù)組，分別是

h[N]：每個(gè)景點(diǎn)的高度

g[N]：正向最長(zhǎng)上升子序列

f[N]：反向最長(zhǎng)上升子序列

main函數(shù)首先要按照ACM的標(biāo)準(zhǔn)輸入方法輸入“景點(diǎn)個(gè)數(shù)”（n）和“每個(gè)景點(diǎn)的海拔高度”(h[i])。

通過(guò)對(duì)所有景點(diǎn)海拔的打印，來(lái)確認(rèn)輸入是正確的。

遍歷從第1個(gè)景點(diǎn)到第n個(gè)景點(diǎn)（i自增的for循環(huán)），依次計(jì)算每個(gè)景點(diǎn)的正向大上升子序列（j自增的for循環(huán)）。

遍歷從第n個(gè)景點(diǎn)到第1個(gè)景點(diǎn)（i自減的for循環(huán)），依次計(jì)算每個(gè)景點(diǎn)的反向大上升子序列（j自減的for循環(huán)）。

遍歷從第1個(gè)景點(diǎn)到第n個(gè)景點(diǎn)，找到?f[i] + g[i] - 1的大值，這個(gè)大值就是我們要求得結(jié)果。

代碼原文

#includeusing namespace std;
const int N = 1010;
int h[N], g[N], f[N];
int main()
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i<= n; i ++) scanf("%d", &h[i]);

    //打印輸入所有景點(diǎn)的海拔
    for(int i = 1; i<= n; i ++) printf("the %d th sight,height is %d\n",i,h[i]);

    //正向最長(zhǎng)上升子序列
    for(int i = 1; i<= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j< i; j ++)
        {
            if(h[i] >h[j])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    //反向最長(zhǎng)上升子序列
    for(int i = n; i; i --)
    {
        g[i] = 1;
        for(int j = n; j >i; j --)
        {
            if(h[i] >h[j])
            {
                g[i] = max(g[i], g[j] + 1);
            }
        }
    }

    int res = 0;
    for(int i = 1; i<= n; i ++)
    {
        res = max(res, f[i] + g[i] - 1);
    }
    printf("Result is %d", res);
    return 0;
}

代碼自測(cè)

C:\Users\zhangyy\CLionProjects\Ctest\cmake-build-debug\Ctest.exe
5
11 22 12 33 22 11
the 1 th sight,height is 11
the 2 th sight,height is 22
the 3 th sight,height is 12
the 4 th sight,height is 33
the 5 th sight,height is 22
Result is 4
Process finished with exit code 0

自測(cè)輸入了5個(gè)山峰的高度，根據(jù)計(jì)算結(jié)果，1,2,4,5景點(diǎn)依次瀏覽是符合題目要求的最優(yōu)解。

總結(jié)

ICPC-ACM題目類型一共有16個(gè)類型：

動(dòng)態(tài)規(guī)劃 · Dynamic Programming
貪心算法 · Greedy
窮舉搜索 · Complete
漫水填充 · Flood Fill
最短路徑 · Shortest Path
回朔搜索技術(shù) · Recarsive Search Techniques
最小生成樹(shù) · Minimum Spanning Tree
背包問(wèn)題 · Knapsack
計(jì)算幾何學(xué) · Computational Geometry
網(wǎng)絡(luò)流 · Network Flow
歐拉回路 · Eulerian Path
凸包問(wèn)題 · Two-Pimensoinal Convex Hull
大數(shù)問(wèn)題 · Bignums
啟發(fā)式搜索 · Hearistic Search
近似搜索 · Approximate Search
雜題 · Ad Hoc Problems

本博客做了一道動(dòng)態(tài)規(guī)劃的簡(jiǎn)單題。

你是否還在尋找穩(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)查看詳情吧

新聞標(biāo)題：ACM動(dòng)態(tài)規(guī)劃題-找最多可能瀏覽的景點(diǎn)數(shù)-創(chuàng)新互聯(lián)
分享鏈接：http://jinyejixie.com/article0/dedsoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、域名注冊(cè)、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站建設(shè)、企業(yè)建站、移動(dòng)網(wǎng)站建設(shè)

廣告

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