• <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>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 1088 滑雪

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

            思路1:
            這題是前段時間微軟筆試的最后一道大題,當時沒想太多,直接簡單DFS,沒想到會超時,結果嘛直接被BS了...太菜啊
            我們從最優解開始分析:
                  設p[1]--p[2]--p[3]...--p[n]即為最長的一條路徑L, p[i]=(xi, yi)
                  對于該路徑L中的一個點p[i], 可以這樣來理解: 到達點p[i]的最長路徑是到達點p[i-1]的最長路徑加1, 并且height(p[i-1])大于height(p[i])
                  因此,我們可以先將輸入地圖按照高度從高到低排序,然后從頭開始依次求出最長路徑
            需要注意的一點:
            下面代碼的第8行需要設置max為1,而不是0, 因為該點可能是最高點(peek)
             1 int 
             2 dp()
             3 {
             4     int total = row*col;
             5     int i, j, x, y, sx, sy, td, max, longest=1;
             6     distance[points[0].x][points[0].y] = 1//highest point
             7     for(i=1; i<total; i++) {
             8         max = 1//max should be set 1, in case points[i] is a peek
             9         x = points[i].x;
            10         y = points[i].y;
            11         for(j=0; j<4; j++) { //four directions
            12             sx = x+dx[j];
            13             sy = y+dy[j];
            14             //points[sx*col+sy] is a higher point around points[i]
            15             if(can_go(sx, sy) && points[i].height<height[sx*col+sy]) { //distance[sx][sy]>0 indicates (sx, sy) a higher point
            16                 td = distance[sx][sy]+1;
            17                 max = max > td ? max : td;
            18             }
            19         }
            20         distance[x][y] = max;
            21         longest = longest > max ? longest : max;
            22     }
            23     return longest;
            24 }

            思路2:
            備忘錄方法
            這里我們換一種看待該問題的方式
            該題有一個很自然的想法,那就是依次枚舉每個點,計算從每個點出發的最長路徑,最后求這些最長路徑的最大值即可
            從一個點p[i]出發的最長路徑是: 從其上下左右四個點出發的最長路徑的最大值加1

            備忘錄方法真的非常好用,而且理解起來也較動態規劃簡單呵呵,原本超時的代碼只要稍加修改就可以AC了
             1 int
             2 dp_memory(int x, int y)
             3 {
             4     if(opt[x][y] != 0//memory, simple but powerful
             5         return opt[x][y];
             6 
             7     int max = 0;
             8     int i, sx, sy, tmp;
             9     for(i=0; i<4; i++) { // four directions
            10         sx = x + dx[i];
            11         sy = y + dy[i];
            12         if(sx>=0 && sx<=row-1 && sy>=0 && sy<=col-1 && map[sx][sy]<map[x][y]) {
            13             tmp = dp_memory(sx, sy);
            14             max = max > tmp ? max : tmp;
            15         }
            16     }
            17     opt[x][y] = max+1;
            18     return opt[x][y];
            19 }
            1 for(i=0; i<row; i++)
            2         for(j=0; j<col; j++) {
            3             tmp = dp_memory(i, j);
            4             max = max > tmp ? max : tmp;
            5         }
            6 

            posted on 2010-06-29 23:56 simplyzhao 閱讀(253) 評論(0)  編輯 收藏 引用 所屬分類: C_動態規劃

            導航

            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            无码国内精品久久人妻麻豆按摩| 久久久久女人精品毛片| 国产综合精品久久亚洲| 久久99精品久久久久久噜噜| 久久精品无码专区免费 | 青青国产成人久久91网| 久久久久国产精品三级网| 久久99精品国产麻豆宅宅| 久久综合九色综合欧美狠狠| 欧美与黑人午夜性猛交久久久| 久久婷婷五月综合色奶水99啪| 精品999久久久久久中文字幕| 日批日出水久久亚洲精品tv| 久久久久久久人妻无码中文字幕爆| 狠狠精品久久久无码中文字幕 | 欧美亚洲色综久久精品国产| 91久久香蕉国产熟女线看| 人妻无码αv中文字幕久久琪琪布 人妻无码精品久久亚瑟影视 | 日本强好片久久久久久AAA| 久久国产成人| 国内精品久久国产大陆| 亚洲色婷婷综合久久| 久久嫩草影院免费看夜色| 日本久久久精品中文字幕| 亚洲精品乱码久久久久久按摩 | 久久久久久久97| 久久无码高潮喷水| 久久国产乱子伦精品免费午夜| 99精品国产在热久久无毒不卡| 久久精品中文无码资源站| 青青久久精品国产免费看| www亚洲欲色成人久久精品| 波多野结衣中文字幕久久| 亚洲精品午夜国产VA久久成人| 欧美成人免费观看久久| a级毛片无码兔费真人久久| 久久久精品午夜免费不卡| 99精品久久精品| 久久久青草青青亚洲国产免观| 97热久久免费频精品99| 青青热久久综合网伊人|