DP动态规划--基础题-滑雪（POJ-1088）

科技2024-05-21 78

DP–基础题-滑雪

原题点这里

题目：

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 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 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为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）的做法：首先如果从某点开始的一个序列是最长的一个递降序列，那么它的后缀头开始的最长序列则应该是该点的后缀序列。 #mermaid-svg-No0R8Zj9HDvte6Gm .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .label text{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .node rect,#mermaid-svg-No0R8Zj9HDvte6Gm .node circle,#mermaid-svg-No0R8Zj9HDvte6Gm .node ellipse,#mermaid-svg-No0R8Zj9HDvte6Gm .node polygon,#mermaid-svg-No0R8Zj9HDvte6Gm .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-No0R8Zj9HDvte6Gm .node .label{text-align:center;fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .node.clickable{cursor:pointer}#mermaid-svg-No0R8Zj9HDvte6Gm .arrowheadPath{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-No0R8Zj9HDvte6Gm .flowchart-link{stroke:#333;fill:none}#mermaid-svg-No0R8Zj9HDvte6Gm .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-No0R8Zj9HDvte6Gm .edgeLabel rect{opacity:0.9}#mermaid-svg-No0R8Zj9HDvte6Gm .edgeLabel span{color:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-No0R8Zj9HDvte6Gm .cluster text{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-No0R8Zj9HDvte6Gm .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-No0R8Zj9HDvte6Gm text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-No0R8Zj9HDvte6Gm .actor-line{stroke:grey}#mermaid-svg-No0R8Zj9HDvte6Gm .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-No0R8Zj9HDvte6Gm #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .sequenceNumber{fill:#fff}#mermaid-svg-No0R8Zj9HDvte6Gm #sequencenumber{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm #crosshead path{fill:#333;stroke:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .messageText{fill:#333;stroke:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-No0R8Zj9HDvte6Gm .labelText,#mermaid-svg-No0R8Zj9HDvte6Gm .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-No0R8Zj9HDvte6Gm .loopText,#mermaid-svg-No0R8Zj9HDvte6Gm .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-No0R8Zj9HDvte6Gm .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-No0R8Zj9HDvte6Gm .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-No0R8Zj9HDvte6Gm .noteText,#mermaid-svg-No0R8Zj9HDvte6Gm .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-No0R8Zj9HDvte6Gm .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-No0R8Zj9HDvte6Gm .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-No0R8Zj9HDvte6Gm .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-No0R8Zj9HDvte6Gm .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .section{stroke:none;opacity:0.2}#mermaid-svg-No0R8Zj9HDvte6Gm .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-No0R8Zj9HDvte6Gm .section2{fill:#fff400}#mermaid-svg-No0R8Zj9HDvte6Gm .section1,#mermaid-svg-No0R8Zj9HDvte6Gm .section3{fill:#fff;opacity:0.2}#mermaid-svg-No0R8Zj9HDvte6Gm .sectionTitle0{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .sectionTitle1{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .sectionTitle2{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .sectionTitle3{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-No0R8Zj9HDvte6Gm .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .grid path{stroke-width:0}#mermaid-svg-No0R8Zj9HDvte6Gm .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-No0R8Zj9HDvte6Gm .task{stroke-width:2}#mermaid-svg-No0R8Zj9HDvte6Gm .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .taskText:not([font-size]){font-size:11px}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-No0R8Zj9HDvte6Gm .task.clickable{cursor:pointer}#mermaid-svg-No0R8Zj9HDvte6Gm .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-No0R8Zj9HDvte6Gm .taskText0,#mermaid-svg-No0R8Zj9HDvte6Gm .taskText1,#mermaid-svg-No0R8Zj9HDvte6Gm .taskText2,#mermaid-svg-No0R8Zj9HDvte6Gm .taskText3{fill:#fff}#mermaid-svg-No0R8Zj9HDvte6Gm .task0,#mermaid-svg-No0R8Zj9HDvte6Gm .task1,#mermaid-svg-No0R8Zj9HDvte6Gm .task2,#mermaid-svg-No0R8Zj9HDvte6Gm .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutside0,#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutside2{fill:#000}#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutside1,#mermaid-svg-No0R8Zj9HDvte6Gm .taskTextOutside3{fill:#000}#mermaid-svg-No0R8Zj9HDvte6Gm .active0,#mermaid-svg-No0R8Zj9HDvte6Gm .active1,#mermaid-svg-No0R8Zj9HDvte6Gm .active2,#mermaid-svg-No0R8Zj9HDvte6Gm .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-No0R8Zj9HDvte6Gm .activeText0,#mermaid-svg-No0R8Zj9HDvte6Gm .activeText1,#mermaid-svg-No0R8Zj9HDvte6Gm .activeText2,#mermaid-svg-No0R8Zj9HDvte6Gm .activeText3{fill:#000 !important}#mermaid-svg-No0R8Zj9HDvte6Gm .done0,#mermaid-svg-No0R8Zj9HDvte6Gm .done1,#mermaid-svg-No0R8Zj9HDvte6Gm .done2,#mermaid-svg-No0R8Zj9HDvte6Gm .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-No0R8Zj9HDvte6Gm .doneText0,#mermaid-svg-No0R8Zj9HDvte6Gm .doneText1,#mermaid-svg-No0R8Zj9HDvte6Gm .doneText2,#mermaid-svg-No0R8Zj9HDvte6Gm .doneText3{fill:#000 !important}#mermaid-svg-No0R8Zj9HDvte6Gm .crit0,#mermaid-svg-No0R8Zj9HDvte6Gm .crit1,#mermaid-svg-No0R8Zj9HDvte6Gm .crit2,#mermaid-svg-No0R8Zj9HDvte6Gm .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-No0R8Zj9HDvte6Gm .activeCrit0,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCrit1,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCrit2,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-No0R8Zj9HDvte6Gm .doneCrit0,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCrit1,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCrit2,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-No0R8Zj9HDvte6Gm .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-No0R8Zj9HDvte6Gm .milestoneText{font-style:italic}#mermaid-svg-No0R8Zj9HDvte6Gm .doneCritText0,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCritText1,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCritText2,#mermaid-svg-No0R8Zj9HDvte6Gm .doneCritText3{fill:#000 !important}#mermaid-svg-No0R8Zj9HDvte6Gm .activeCritText0,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCritText1,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCritText2,#mermaid-svg-No0R8Zj9HDvte6Gm .activeCritText3{fill:#000 !important}#mermaid-svg-No0R8Zj9HDvte6Gm .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-No0R8Zj9HDvte6Gm g.classGroup text .title{font-weight:bolder}#mermaid-svg-No0R8Zj9HDvte6Gm g.clickable{cursor:pointer}#mermaid-svg-No0R8Zj9HDvte6Gm g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-No0R8Zj9HDvte6Gm g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-No0R8Zj9HDvte6Gm .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-No0R8Zj9HDvte6Gm .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-No0R8Zj9HDvte6Gm .dashed-line{stroke-dasharray:3}#mermaid-svg-No0R8Zj9HDvte6Gm #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm .commit-id,#mermaid-svg-No0R8Zj9HDvte6Gm .commit-msg,#mermaid-svg-No0R8Zj9HDvte6Gm .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-No0R8Zj9HDvte6Gm g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-No0R8Zj9HDvte6Gm g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-No0R8Zj9HDvte6Gm g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-No0R8Zj9HDvte6Gm .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-No0R8Zj9HDvte6Gm .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-No0R8Zj9HDvte6Gm .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-No0R8Zj9HDvte6Gm .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-No0R8Zj9HDvte6Gm .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-No0R8Zj9HDvte6Gm .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-No0R8Zj9HDvte6Gm .edgeLabel text{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-No0R8Zj9HDvte6Gm .node circle.state-start{fill:black;stroke:black}#mermaid-svg-No0R8Zj9HDvte6Gm .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-No0R8Zj9HDvte6Gm #statediagram-barbEnd{fill:#9370db}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-state .divider{stroke:#9370db}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-No0R8Zj9HDvte6Gm .note-edge{stroke-dasharray:5}#mermaid-svg-No0R8Zj9HDvte6Gm .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-No0R8Zj9HDvte6Gm .error-icon{fill:#522}#mermaid-svg-No0R8Zj9HDvte6Gm .error-text{fill:#522;stroke:#522}#mermaid-svg-No0R8Zj9HDvte6Gm .edge-thickness-normal{stroke-width:2px}#mermaid-svg-No0R8Zj9HDvte6Gm .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-No0R8Zj9HDvte6Gm .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-No0R8Zj9HDvte6Gm .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-No0R8Zj9HDvte6Gm .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-No0R8Zj9HDvte6Gm .marker{fill:#333}#mermaid-svg-No0R8Zj9HDvte6Gm .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-No0R8Zj9HDvte6Gm { color: rgba(0, 0, 0, 0.75); font: ; } A B C D K E F G

同理反推，如图，若C的最长递降序列为C-D-K，F的最长递归序列为F-G，则E的最长递降序列是只能从F后缀和C后缀里挑，经过对比可以得到E的最长递归序列为E-C-D-K。这样通过自低到高的反推dp则可以得到所有点的最长递降序列长度。

由于要对点的高低进行排序，我使用了结构数组和stl的自定义sort

不多说，上代码

参考AC代码：

#include<iostream> #include<algorithm> using namespace std; typedef struct grid { int x, y; int h; grid() {}; grid(int x0, int y0, int h0) : x(x0), y(y0), h(h0) { }; }; bool cmp(grid a, grid b) { return a.h < b.h; } int dx[5] = { 1,0,-1,0 }; int dy[5] = { 0,-1,0,1 }; int main() { int R, C; grid g[10010]; int h[101][101];//存放该点的高度 int dp[101][101];//存放该点开始的最长滑雪距离 int k = 0; cin >> R >> C; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cin >> h[i][j]; dp[i][j] = 1;//dp初始化为1,表示所有点的初始最长滑雪距离为1 g[k++] = grid(i, j, h[i][j]); } } sort(g, g + C * R, cmp); for (int i = 0; i < C * R; i++) { //int nowh = g[i].h; for (int d = 0; d < 4; d++) {//遍历四邻点 int xi = g[i].x + dx[d]; int yi = g[i].y + dy[d]; if (xi >= 0 && xi < R && yi>=0 && yi < C) { if (h[xi][yi]<g[i].h && dp[xi][yi] + 1>dp[g[i].x][g[i].y]) {//如果该邻点为低点则进行dp dp[g[i].x][g[i].y] = dp[xi][yi] + 1;//更新dp数组 } } } } int MAX = -1; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { MAX = max(dp[i][j], MAX);//找到最大滑雪距离值 } } cout << MAX << endl; return 0; }

总结：本题应该很轻松就能看出其dp的属性并得出递推关系。稍加打磨并利用好结构数组便能很轻松地解出来，我第一次比赛里做居然没能AC

有兴趣的同学dp做完后可以试试搜索的做法，后续学习过程中或许我也会给出搜索的解法。

Processed: 0.019, SQL: 8