題干：

Help Jimmy" 是在下圖所示的場景上完成的游戲。?

?

場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。?

Jimmy老鼠在時刻0從高于所有平臺的某處開始下落，它的下落速度始終為1米/秒。當Jimmy落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1米/秒。當Jimmy跑到平臺的邊緣時，開始繼續下落。Jimmy每次下落的高度不能超過MAX米，不然就會摔死，游戲也會結束。?

設計一個程序，計算Jimmy到底地面時可能的最早時間。?

Input

第一行是測試數據的組數t（0 <= t <= 20）。每組測試數據的第一行是四個整數N，X，Y，MAX，用空格分隔。N是平臺的數目（不包括地面），X和Y是Jimmy開始下落的位置的橫豎坐標，MAX是一次下落的最大高度。接下來的N行每行描述一個平臺，包括三個整數，X1[i]，X2[i]和H[i]。H[i]表示平臺的高度，X1[i]和X2[i]表示平臺左右端點的橫坐標。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐標的單位都是米。?

Jimmy的大小和平臺的厚度均忽略不計。如果Jimmy恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數據保證問題一定有解。?

Output

對輸入的每組測試數據，輸出一個整數，Jimmy到底地面時可能的最早時間。

?

AC代碼1：

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int INF = 0x3f3f3f3f; int n,x,y,maxx; int dp[1005][2];//fg=0代表左邊，fg=1代表右邊 struct Node {int l,r,h; } node[1005]; bool cmp(const Node & a,const Node & b) {return a.h < b.h; } int dfs(int cur,int fg) {if(cur == 1) return 0;if(dp[cur][fg] != -1) return dp[cur][fg];if(cur == 1) {return 0;}int ans = INF;if(dp[cur][fg] != -1) {return dp[cur][fg];}int temp = cur; for(int i = cur-1; i>=1; i--) {temp=i;if(node[cur].h - node[i].h > maxx) break;if(fg==0) {if(node[i].l <= node[cur].l && node[i].r >= node[cur].l) {ans = min(dfs(i,0)+node[cur].l-node[i].l,dfs(i,1) +node[i].r-node[cur].l );break;}} else {if(node[i].r >= node[cur].r && node[i].l <= node[cur].r) {ans = min(dfs(i,0)+node[cur].r-node[i].l,dfs(i,1)+node[i].r-node[cur].r);break;}}}if(ans == INF) {if(node[cur].h <= maxx) return dp[cur][fg] = 0;else return dp[cur][fg] = ans;}else return dp[cur][fg] = ans; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%d%d",&n,&x,&y,&maxx);memset(dp,-1,sizeof (dp));for(int i = 1; i<=n; i++) {scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].h);}sort(node+1,node+n+1,cmp);int ok=n+1; // node[ok].h = y;node[ok].l=node[ok].r=x;for(int i = n; i>=1; i--) {if(node[i].r >= x && node[i].l <= x) {ok=i;break;}}if(ok == n+1) {printf("%d\n",y);}else {int ans = min(dfs(ok,1) + node[ok].r-x,dfs(ok,0) + x-node[ok].l) + y; // int ans = min(dfs(ok,1),dfs(ok,0)) + y;printf("%d\n",ans);}} return 0 ;} //1 //1 //2 3 //100 //5 6 1

AC代碼2：

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int INF = 0x3f3f3f3f; int n,x,y,maxx; int dp[1005][2];//fg=0代表左邊，fg=1代表右邊 struct Node {int l,r,h; } node[1005]; bool cmp(const Node & a,const Node & b) {return a.h < b.h; } int dfs(int cur,int fg) {if(cur == 1) return 0;if(dp[cur][fg] != -1) return dp[cur][fg]; // int minn = 0x3f3f3f3f,flag=0;//0左 1右 // int temp=cur;int ans = INF;int temp = cur; for(int i = cur-1; i>=1; i--) {temp=i;if(node[cur].h - node[i].h > maxx) break;if(fg==0) {if(node[i].l <= node[cur].l && node[i].r >= node[cur].l) {ans = min(dfs(i,0)+node[cur].l-node[i].l,dfs(i,1) +node[i].r-node[cur].l );break;}} else {if(node[i].r >= node[cur].r && node[i].l <= node[cur].r) {ans = min(dfs(i,0)+node[cur].r-node[i].l,dfs(i,1)+node[i].r-node[cur].r);break;}}}if(ans == INF) {if(node[cur].h <= maxx) return dp[cur][fg] = 0;else return dp[cur][fg] = ans;}else return dp[cur][fg] = ans; // if(ans == INF) { // if(temp == 1) { // if(node[cur].h > maxx) return dp[cur][fg] = ans; // else return dp[cur][fg] = 0; // } // return dp[cur][fg] = ans; // } // else return dp[cur][fg] = ans; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%d%d",&n,&x,&y,&maxx);memset(dp,-1,sizeof (dp));for(int i = 1; i<=n; i++) {scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].h);}sort(node+1,node+n+1,cmp);int ok=n+1;node[ok].h = y;node[ok].l=node[ok].r=x; // for(int i = n; i>=1; i--) { // if(node[i].r >= x && node[i].l <= x) { // ok=i;break; // } // } // int ans = min(dfs(ok,1) + node[ok].r-x,dfs(ok,0) + x-node[ok].l) + y;int ans = min(dfs(ok,1),dfs(ok,0)) + y;printf("%d\n",ans);} return 0 ;}

錯誤代碼：

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int n,x,y,maxx; int dp[1005]; struct Node {int l,r,h; } node[1005]; bool cmp(const Node & a,const Node & b) {return a.h < b.h; } int dfs(int cur,int curx,int curh) {if(curh == 0) return 0;if(cur < 0) return 0;if(dp[cur] != -1) return dp[cur];int minn = 0x3f3f3f3f;for(int i = cur-1; i>=1; i--) {if(curh - node[i].h > maxx) break;if(node[i].l <= node[cur].l) minn = min(minn,dfs(i,node[cur].l,node[i].h)+node[cur].l-curx);if(node[i].r >= node[cur].r) minn = min(minn,dfs(i,node[cur].r,node[i].h)+node[cur].r-curx);}return dp[cur] = minn; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%d%d",&n,&x,&y,&maxx);memset(dp,-1,sizeof (dp));for(int i = 1; i<=n; i++) {scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].h);}sort(node+1,node+n+1,cmp);printf("%d\n",dfs(n,x,node[n].h));} // 18653293769return 0 ;}

總結：

? ?幾個地方是真的坑，首先這個錯誤代碼，記憶化搜素的設計狀態我就沒搞明白（因為后來我通過觀察發現一維dp表示不了所有狀態），于是dfs中亂設了一堆參數，結果顯然都沒用。

? ?其二，函數內部，顯然要break，不能不加break，因為有上一個臺子擋住了，后面即使有符合的，也不能跳上去了，所以要break。

? ?其三，要處理好到地面的那一步，一定是直接跳過去的（也就是 一定ans==INF），所以return的時候不能直接retrun dp[cur][fg] = ans;而應該判斷是否ans==INF 如果等于的話，也就說明是到地面了，要dp[cur][fg] = 0;才可以。

? ?其四，有個處理技巧，讓出發點當成一個新的平臺，這樣直接統一形式就可以了。不然的話，就跟AC代碼1一樣，先判斷是否從出發點可以直接落到地面上，特判一下這個條件才可以。

? 其五，有個技巧，就是高度都最后統一算，直接+y就可以了，這樣減少了代碼出錯概率。

? 其六，遞歸函數中的狀態轉移要想清楚，到底是由哪些狀態轉移而來，或者想，可以轉移到哪些狀態去。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【POJ - 1661】Help Jimmy（记忆化搜索，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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