青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

POJ 1088 動態規劃之經典問題——滑雪

動態規劃之經典問題——滑雪解題報告

                                           

原題鏈接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

Description

Michael喜歡滑雪百這并不奇怪,因為滑雪的確很刺激。可是為了獲得速度,滑的區域必須向下傾斜,而且當你滑到坡底,你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區域中最長底滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。下面是一個例子

4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一個人可以從某個點滑向上下左右相鄰四個點之一,當且僅當高度減小。在上面的例子中,一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上,這是最長的一條。

Input

輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)。下面是R行,每行有C個整數,代表高度h,0<=h<=10000。

Output

輸出最長區域的長度。

Sample Input

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

Sample Output

25

個人心得:記得前段時間曾經做過一個求最長下降子序列的題(相信大家都做過該題,故不另附原題),如果說說那道題是dp問題的基礎,那么這道題就可以稱得上是求最長下降子序列的變種或者更確切的說是一種升華!

對比來看,前者是求最長下降子序列在一維條件下的解,而1088滑雪這道題則是將此下降問題至于二維平面的背景下。相信弄明白這道題是非常有必要的,因為它不僅升華了我們對該類問題的理解,而且能啟發我們用同樣的思維方式去解決更多動態規劃的問題。

 

 

題目意思其實很簡單,給出一個二維數組,在其中找出一個點,是它能找到一條高度依次下降的路徑并使得這條路徑最長。

算法:開一個二維數組height記錄每個點的高度,一個二維數組len記錄每個點能搜索到的最長下降子序列的長度(初始值全為零),一個結構體數組dot line[20000]記錄每個點的坐標(x,y)和高度值 h.

先將每個點的記錄信息保存在結構體數組中。然后以高度由低到高的順序排序,初始狀態下指針就位于結構體數組的起始位置。

接著順序的掃描此結構體數組內的信息,因為已經排好序,所以高度是一次遞增的,這樣做的好處是只需要朝著一個方向搜索,而且還可以有效避免越界的問題。

當指針每指向一個結構體個體時,我們均可以找到該點在height數組里的位置,如果存在任意一個點,在它周圍的四個方向上而且高度比該點大且這個任意點的最長下降子序列小于或等于該店的長度。那么這個任意點的最長下降子序列的長度就+1;

等到結構體數組掃描完成,再去遍歷len這個二維數組,求出最大值即為所求;

 

 

 

CODE:

 

#include<iostream>

#include
<cmath>

#include
<cstring>

#include
<cstdio>

#include
<algorithm>

using namespace std;

 

 

struct dot//創建一個結構體存儲每個點的信息

{

    
int x;

    
int y;

    
int h;

}
;

dot line[
20000]; //將每個點存入該結構體數組

int height[120][120]; //用于存儲input

int len[120][120];  //dp數組,存儲每個點的最優解

int cmp( const void *a ,const void *b) //快速排序的參考函數

{

 

    
if((*(dot *)a).h>(*(dot *)b).h)

        
return 1;

    
else return -1;

 

}


int main ()

{

    
int m,n;

    cin
>>m>>n;

    
int i,j;

    
int flag=-1;

    
int max=0;

    
for(i=1;i<=m;i++)

    
{

 

        
for(j=1;j<=n;j++)

        
{

            flag
++;

            scanf(
"%d",&height[i][j]);

            line[flag].x
=i;

            line[flag].y
=j;

            line[flag].h
=height[i][j];

        }


    }
 //這個雙層循環用來完成數據收集的工作

    qsort(line,m
*n,sizeof(line[0]),cmp); //對結構體的h參數進行排序

    
for(i=0;i<m*n;i++)

    
{

    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y+1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y+1])

        
{

            len[line[i].x][line[i].y
+1]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x+1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x+1][line[i].y])

        
{

            len[line[i].x
+1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y-1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y-1])

        
{

            len[line[i].x][line[i].y
-1]=len[line[i].x][line[i].y]+1;

        }


        
if (height[line[i].x][line[i].y]<height[line[i].x-1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x-1][line[i].y])

        
{

            len[line[i].x
-1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    }
 //動態規劃過程

    
for(i=1;i<=m;i++)

    
{

        
for(j=1;j<=n;j++)

        
{

 

           

            
if(len[i][j]>max)

                max
=len[i][j];

        }


    }
 //遍歷len數組,求出最大值

    cout
<<max+1<<endl;// 因為初始值是0,所以最后要加一

    
return 0;

}


 

 

最后不得不說,動態規劃的確是一個值得研究的問題,相比于遞歸,他能夠節省大量的運行時間。

鑒于現在還處于學習的初級階段,如果有所不足,還請老師和學長們多多指點.

Thank you~

posted on 2009-02-19 13:00 abilitytao 閱讀(10779) 評論(13)  編輯 收藏 引用

評論

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-02-19 21:43 ghbxx

PKU上還有一個題目和他很相似的,希望樓主能做一下。我在大學的時候做過的。  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-02-19 23:10 abilitytao

@ghbxx
請問學長你說的是求長下降子序列嗎
還是最大子段和?
  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪[未登錄] 2009-02-22 20:30 Philip85517

更像是一個迭代的過程。Ps.四個方向的搜索寫的太長了,完全可以用數組來表示方向,會快很多。
相似的題目:FatMouse and Cheese, Monkey and banana
有興趣再看看那個Fourier's Lines,個人感覺不錯,是一個比較好的Dp
  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪[未登錄] 2009-02-22 20:41 abilitytao

@Philip85517
謝謝
  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-04-21 17:56 Wpl

我也在努力學習DP,感覺好難啊  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-04-23 17:59 你好

好感謝,真了無頭緒之中  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-06-11 11:23 hfie

思路很強大,但不像是最長下降子序列  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2009-11-15 13:01 PhiloEve

不需要調用那么多的庫吧?  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2010-11-25 11:30 aaa

您好,我感覺您用的是搜索啊,不是DP啊,我是初學者,不了解,請您指教
xuzhenjetxu@gmail.com  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2011-06-17 01:10 Dev|il

@aaa
是DP  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2012-05-24 00:49 hacker003

感謝樓主,此題確實是好題。
不過樓主的搜索確實可以把代碼簡化一下  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪[未登錄] 2012-05-24 14:35 abilitytao

@hacker003
剛開始學的時候寫的 比較水 呵呵 見笑了...  回復  更多評論   

# re: POJ 1088 動態規劃之經典問題——滑雪 2013-07-13 14:08 aaa

樓主提交過么???WA啊。。。有考慮過有兩條相等的路么???比如
1 2
2 3
你的程序算出來是3
但應該是2 啊  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            红桃av永久久久| 欧美精品二区三区四区免费看视频| 欧美午夜不卡在线观看免费 | 欧美成人在线免费视频| 久久久噜噜噜久久中文字免| 一区二区亚洲欧洲国产日韩| 久久亚洲精品伦理| 免费高清在线一区| 99视频精品免费观看| 一区二区av在线| 国产亚洲精品福利| 久久综合久久美利坚合众国| 乱中年女人伦av一区二区| 亚洲精品一区二区三区福利| 夜久久久久久| 国产一区二区三区精品欧美日韩一区二区三区 | 快射av在线播放一区| 日韩亚洲视频| 国产精品一区二区你懂得| 久久狠狠亚洲综合| 久久国产精品久久国产精品| 在线视频国产日韩| 91久久综合亚洲鲁鲁五月天| 欧美日韩国产另类不卡| 午夜免费日韩视频| 美女主播精品视频一二三四| 日韩一区二区精品葵司在线| 亚洲伊人一本大道中文字幕| 在线精品视频免费观看| 一本久道综合久久精品| 国产欧美一区二区视频| 美女成人午夜| 国产精品二区在线| 久久综合久色欧美综合狠狠| 欧美日韩18| 农村妇女精品| 国产精品久久久久久久7电影| 久久精品国产免费观看| 欧美激情亚洲另类| 久久只有精品| 国产伦精品一区二区三区视频黑人| 欧美在线一级视频| 久久国产精品第一页| 亚洲一区二区三区高清不卡| 久久这里有精品视频| 欧美一区二区三区四区高清| 欧美了一区在线观看| 午夜日韩激情| 欧美色区777第一页| 欧美va亚洲va国产综合| 国产亚洲成年网址在线观看| 亚洲久久一区二区| 99re66热这里只有精品4| 久久精品综合一区| 久久精品理论片| 国产精品毛片在线| 一本色道久久加勒比88综合| 亚洲精品久久久久久久久| 久久婷婷国产综合精品青草| 久久精品亚洲精品国产欧美kt∨| 欧美日韩在线免费观看| 亚洲国产欧美一区| 亚洲高清一二三区| 久久久久久久久久久一区| 久久久国产午夜精品| 国产午夜精品久久久久久久| 中日韩午夜理伦电影免费| 中文在线不卡| 欧美日韩综合在线免费观看| 亚洲精品三级| 亚洲小少妇裸体bbw| 欧美日韩在线一二三| 夜夜嗨av一区二区三区| 亚洲校园激情| 国产欧美在线播放| 久久er99精品| 欧美激情精品久久久久久变态 | 欧美性生交xxxxx久久久| 99视频在线精品国自产拍免费观看 | 亚洲国产高清高潮精品美女| 亚洲三级网站| 欧美精品在线观看91| 亚洲精品中文字幕女同| 亚洲校园激情| 国产一区二区三区免费观看| 性刺激综合网| 欧美成人三级在线| 亚洲日本电影| 国产精品v日韩精品v欧美精品网站| 这里只有精品在线播放| 欧美一区二区三区免费在线看| 国产日韩精品一区二区| 欧美在线亚洲在线| 亚洲成色777777在线观看影院| 亚洲精品中文字| 国产精品久久久久久超碰| 欧美一区二区黄色| 亚洲高清免费视频| 亚洲资源在线观看| 一区二区在线观看av| 欧美国产日韩在线观看| 亚洲天堂免费观看| 免费成人性网站| 亚洲免费一区二区| 亚洲春色另类小说| 国产乱码精品| 欧美激情视频网站| 欧美一级大片在线观看| 亚洲国产一区二区三区青草影视| 午夜精品久久久久久久男人的天堂| 狠狠操狠狠色综合网| 欧美色另类天堂2015| 欧美专区日韩专区| 一区二区三区欧美视频| 欧美a级理论片| 性欧美8khd高清极品| 99国产精品久久久久久久| 国产亚洲激情视频在线| 欧美日韩精品一区二区在线播放| 久久高清国产| 亚洲自拍偷拍福利| 亚洲精品一区二区三区樱花| 免费日韩精品中文字幕视频在线| 午夜精品影院在线观看| 夜夜嗨av一区二区三区网页| 亚洲第一色在线| 国产一区二区激情| 国产精品性做久久久久久| 欧美激情精品久久久| 久久深夜福利| 久久久不卡网国产精品一区| 亚洲欧美三级在线| 一区二区三区福利| 99精品国产一区二区青青牛奶| 欧美高清日韩| 亚洲第一网站| 亚洲福利视频一区| 欧美国产激情二区三区| 欧美二区不卡| 欧美国产欧美亚洲国产日韩mv天天看完整 | 国产午夜精品久久久久久久| 国产精品人人做人人爽| 99在线视频精品| 久久免费午夜影院| 亚洲美女诱惑| 亚洲精品久久| 亚洲激情一区二区三区| 亚洲日本va在线观看| 在线看国产日韩| 狠狠色综合一区二区| 国产一在线精品一区在线观看| 国产欧美成人| 韩日在线一区| 亚洲大胆av| 日韩午夜电影av| 中文久久精品| 亚洲欧美日韩国产综合在线| 午夜综合激情| 久久久人成影片一区二区三区观看 | 亚洲欧美日韩网| 午夜精品福利视频| 久久九九免费| 欧美成人免费va影院高清| 亚洲国产另类精品专区| 日韩视频免费观看高清完整版| 99精品欧美一区二区三区| 亚洲在线观看视频| 欧美一区二区在线看| 久久国产精品色婷婷| 欧美电影免费| 国产精品夜夜夜| 在线播放日韩专区| 一区二区日韩免费看| 亚洲性图久久| 美女国内精品自产拍在线播放| 亚洲第一页在线| 亚洲午夜视频在线观看| 久久久噜噜噜久久狠狠50岁| 欧美精品精品一区| 国产亚洲va综合人人澡精品| 亚洲日本va午夜在线影院| 午夜精品久久久久影视| 欧美成人午夜激情| 亚洲一区二区三区涩| 欧美91大片| 国产日韩av一区二区| 亚洲美洲欧洲综合国产一区| 欧美一级艳片视频免费观看| 欧美电影免费网站| 性欧美暴力猛交另类hd| 欧美激情一区二区久久久| 国产一级精品aaaaa看| 日韩天堂在线视频| 久久久久久高潮国产精品视| 中国成人亚色综合网站| 欧美激情一区二区久久久| 136国产福利精品导航| 久久大综合网| 亚洲永久视频| 国产精品二区三区四区|