動態規劃5--滑雪

一、心得

找路徑時，遞推的方法和遞歸一樣，也是知道遞推表達式之后就特別好寫了
也是直接把遞推表達式寫進循環里面就好了
遞推和遞推寫法的區別：
遞歸是調用的系統棧，遞推沒有調用棧，其它一模一樣了

?

二、題目和分析

滑雪：
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更長。事實上，這是最長的一條。輸入輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)。下面是R行，每行有C個整數，代表高度h，0<=h<=10000。輸出輸出最長區域的長度。
輸入
輸入的第一行表示區域的行數R和列數C
(1 <= R,C <= 100)。下面是R行，每行有C個整數，
代表高度h，0<=h<=10000。
輸出
輸出最長區域的長度。
樣例輸入
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
樣例輸出
25

?

先定義結構體把每個點的x，y和h都裝起來，依次儲存每個點。
那這個問題就從二維化成了一維。
按每個點高度從大到小排好。
其實就變成了不下降子序列那個問題。
具體做法：
我按高度依次往后面找，看看后面的點是否滿足點在這個點旁邊的規則。
滿足的話就路徑長度加1。

?

L(i,j)表示從點(i,j)出發的最長滑行長度。
一個點(i,j), 如果周圍沒有比它低的點，L(i,j) = 1
否則
遞推公式： L(i,j) 等于(i,j)周圍四個點中,比(i,j)低，且L值最大的那個點的L值，再加1
復雜度：O(n2)

解法1） “人人為我”式遞推
L(i,j)表示從點(i,j)出發的最長滑行長度。
一個點(i,j), 如果周圍沒有比它低的點，L(i,j) = 1
將所有點按高度從小到大排序。每個點的 L 值都初始化為1
從小到大遍歷所有的點。經過一個點(i,j)時，用遞推公式求L(i,j)

?

解法2） “我為人人”式遞推
L(i,j)表示從點(i,j)出發的最長滑行長度。
一個點(i,j), 如果周圍沒有比它低的點，L(i,j) = 1
將所有點按高度從小到大排序。每個點的 L 值都初始化為1
從小到大遍歷所有的點。經過一個點(i,j)時，要更新他周圍的，比它高的點的L值。例如：
if H(i+1,j) > H(i,j) // H代表高度
L(i+1,j) = max(L(i+1,j),L(i,j)+1)

三、代碼和結果

1 /* 2 心得： 3 找路徑時，遞推的方法和遞歸一樣，也是知道遞推表達式之后就特別好寫了 4 也是直接把遞推表達式寫進循環里面就好了 5 遞推和遞推寫法的區別： 6 遞歸是調用的系統棧，遞推沒有調用棧，其它一模一樣了 7 8 將題目轉化為了求不下降子序列的長度 9 */ 10 #include <iostream> 11 #include <algorithm> 12 #define Max 105 13 using namespace std; 14 15 struct node{//表示每一個點 16 int r;//每一個點的行位置 17 int c;//每一個點的列位置 18 int h;//每一個點的高 19 }; 20 //排序規則，將結構從大到小排序 21 int my_comp(const node &p1,const node &p2){ 22 return p1.h>p2.h; 23 //本來順序是p1,p2，如果p1的高大于p2的高，我們就不交換 24 } 25 node a[Max*Max];//儲存每一個節點，按高度排序后將二維數組化成了一維數組 26 //dp[i]表示第i個點對應的最長區域的長度 27 int R,C,dp[Max*Max];//R表示行，R表示列 28 int pre[Max*Max];//記錄每個點的路徑 29 int maxn=0,maxn_i=R*C;//記錄最長路徑對應的點的值和編號 30 31 void input();//輸入數據 32 void test_input(int R,int C);//測試輸入數據 33 void init_dp();//動態規劃前的初始化，初始化dp數組 34 void dpFunction();//dp操作 35 bool isClose(node a,node b);//判斷兩個點是否相連 36 void printRoad1(int i);//遞歸方法打印路徑 37 void printRoad2(int i);//遞推方法打印路徑 38 39 40 41 42 int main(){ 43 freopen("in.txt","r",stdin); 44 45 input();//輸入數據 46 47 sort(a+1,a+R*C+1,my_comp);//對每個點按高度進行排序 48 //test_input(R,C); //測試輸入數據 49 init_dp();//動態規劃前的初始化，初始化dp數組 50 dpFunction();//dp操作 51 //遞歸找路徑 52 printRoad1(pre[maxn_i]); 53 cout<<a[maxn_i].r<<","<<a[maxn_i].c<<endl;//輸出第一個點 54 55 //遞推找路徑 56 //cout<<a[maxn_i].r<<","<<a[maxn_i].c;//輸出第一個點 57 //printRoad2(pre[maxn_i]);//輸出后面的點 58 return 0; 59 } 60 61 //遞推方法打印路徑 62 void printRoad2(int i){ 63 /* 64 遞推表達式是： 65 如果pre[i]==0，表示是起始點，return 66 如果不是0，遞歸唄 67 */ 68 /* 69 找路徑時，遞推的方法和遞歸一樣，也是知道遞推表達式之后就特別好寫了 70 也是直接把遞推表達式寫進循環里面就好了 71 遞推和遞推寫法的區別： 72 遞歸是調用的系統棧，遞推沒有調用棧，其它一模一樣了 73 */ 74 while(true){ 75 if(i==0){ 76 break; 77 } 78 else{ 79 cout<<"-->"<<a[i].r<<","<<a[i].c; 80 i=pre[i]; 81 } 82 } 83 } 84 85 //遞歸方法打印路徑 86 void printRoad1(int i){ 87 /* 88 遞推表達式是： 89 如果pre[i]==0，表示是起始點，return 90 如果不是0，遞歸唄 91 */ 92 if(i==0){ 93 return ; 94 } 95 else{ 96 printRoad1(pre[i]); 97 cout<<a[i].r<<","<<a[i].c<<"-->"; 98 } 99 } 100 101 //dp操作 102 void dpFunction(){ 103 //從高往低走，如果靠近，上下左右相鄰四個點之一，最長區域就加1 104 for(int i=1;i<=R*C;i++){ 105 for(int j=1;j<i;j++){ 106 if(isClose(a[i],a[j])){ 107 if(dp[j]+1>=dp[i]){ 108 dp[i]=dp[j]+1; 109 pre[i]=j; 110 } 111 } 112 } 113 } 114 //路徑最長的點并不是一定從最后面出來的那個點，所以cout<<dp[R*C]<<endl;是不對的 115 //還要找到dp里面那個最大的值，和那個值對應的編號 116 117 for(int i=1;i<=R*C;i++){ 118 if(dp[i]>maxn){ 119 maxn=dp[i]; 120 maxn_i=i; 121 } 122 } 123 //cout<<maxn<<" "<<maxn_i<<endl; 124 cout<<maxn<<endl; 125 126 } 127 128 //判斷兩個點是否相連 129 bool isClose(node a,node b){ 130 /* 131 r-1 132 c-1 r,c c+1 133 r+1 134 */ 135 //對應上下左右, 136 //r在前列子在后 137 int direction[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; 138 // cout<<direction[0][0]<<endl; 139 // cout<<direction[0][1]<<endl; 140 // cout<<direction[1][0]<<endl; 141 // cout<<direction[1][1]<<endl; 142 143 for(int i=0;i<4;i++){ 144 //a在中心 145 if((a.r+direction[i][0]==b.r)&&(a.c+direction[i][1]==b.c)){ 146 return true; 147 } 148 } 149 return false; 150 151 } 152 153 //動態規劃前的初始化，初始化dp數組 154 void init_dp(){ 155 for(int i=1;i<=R*C;i++){ 156 dp[i]=1; 157 } 158 } 159 160 //輸入數據 161 void input(){ 162 cin>>R>>C; 163 int num=1; 164 for(int i=1;i<=R;i++){ 165 for(int j=1;j<=C;j++){ 166 a[num].r=i; 167 a[num].c=j; 168 cin>>a[num++].h; 169 } 170 } 171 } 172 173 //測試輸入數據 174 void test_input(int R,int C){ 175 for(int i=1;i<=R*C;i++){ 176 cout<<a[i].r<<" "<<a[i].c<<" "<<a[i].h<<endl; 177 } 178 }

總結

以上是生活随笔為你收集整理的动态规划5--滑雪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。