題目描述

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

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

思路

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

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

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

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

h[N]：每個景點的高度

g[N]：正向最長上升子序列

f[N]：反向最長上升子序列

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

通過對所有景點海拔的打印，來確認(rèn)輸入是正確的。

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

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

遍歷從第1個景點到第n個景點，找到?f[i] + g[i] - 1的大值，這個大值就是我們要求得結(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]);

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

    //正向最長上升子序列
    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);
            }
        }
    }

    //反向最長上升子序列
    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:\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

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

總結(jié)

ICPC-ACM題目類型一共有16個類型：

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

本博客做了一道動態(tài)規(guī)劃的簡單題。

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

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

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

廣告

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