題目：

蒜頭君在玩一款逃生的游戲。在一個 $n\times m$ 的矩形地圖上，蒜頭位于其中一個點。地圖上每個格子有加血的藥劑，和掉血的火焰，藥劑的藥效不同，火焰的大小也不同，每個格子上有一個數(shù)字，如果格子上的數(shù)字是正數(shù)說明是一個藥劑代表增加的生命值，如果是負(fù)數(shù)說明是火焰代表失去的生命值。

蒜頭初始化有 v 點血量，他的血量上限是 c，任何時刻他的生命值都不能大于血量上限，如果血量為 0 則會死亡，不能繼續(xù)游戲。

矩形地圖上的四個角(1,1)，(1,m)，(n,1)，(n,m) 為游戲的出口。游戲中只要選定了一個出口，就必須朝著這個方向走。例如，選擇了左下的出口，就只能往左和下兩個方向前進(jìn)，選擇了右上的出口，就只能往右和上兩個方向前進(jìn)，左上和右下方向的出口同理。

如果成功逃生，那么剩余生命值越高，則游戲分?jǐn)?shù)越高。為了能拿到最高分，請你幫忙計算如果成功逃生最多能剩余多少血量，如果不能逃生輸出?1。

輸入格式

第一行依次輸入整數(shù) $nn，mm，xx，yy，vv，cc（1<n,m\le 1000，1\le x\le n，1\le y\le m，1\le v\le c\le 10000$）, 其中 n, mn,m 代表地圖大小，(x, y)(x,y) 代表蒜頭君的初始位置，vv 代表蒜頭的初始化血量，cc 代表蒜頭的生命值上限。

接下來 nn 行，每行有 mm 個數(shù)字，代表地圖信息（每個數(shù)字的絕對值不大于 100，地圖中蒜頭君的初始位置的值一定為 0）。

輸出格式

一行輸出一個數(shù)字，代表成功逃生最多剩余的血量，如果失敗輸出 -1?1。

輸出時每行末尾的多余空格，不影響答案正確性

要求使用「文件輸入輸出」的方式解題，輸入文件為 escape.in，輸出文件為 escape.out

樣例輸入

4 4 3 2 5 10
1 2 3 4
-1 -2 -3 -4
4 0 2 1
-4 -3 -2 -1

樣例輸出

10

分析：

• 這里需要分開枚舉四個方向。
• 另外還需要處理一個問題，中途，當(dāng)遇到某個 dp[i][j] 小于等于 0 的時候，把 dp[i][j]賦值為 -inf，可以讓這個位置就不會轉(zhuǎn)移出后繼狀態(tài)了。當(dāng) dp[i][j]大于 c 的時候需要把 dp[i][j]dp[i][j] 賦值為 c(題目中說：他的血量上限是 c，任何時刻他的生命值都不能大于血量上限)

AC代碼：

#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; const int M=1e3+10; const int inf=0x3f3f3f3f; int n,m,x,y,v,c; int mp[M][M],dp[M][M]; int main(){freopen("escape.in", "r", stdin);freopen("escape.out", "w", stdout);cin>>n>>m>>x>>y>>v>>c;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];dp[x][y]=v;for(int i=x;i>=1;i--)for(int j=y;j>=1;j--){if(i==x&&j==y) continue;else if(i==x) dp[i][j]=dp[i][j+1]+mp[i][j];else if(j==y) dp[i][j]=dp[i+1][j]+mp[i][j];else dp[i][j]=max(dp[i+1][j],dp[i][j+1])+mp[i][j];if(dp[i][j]<=0)dp[i][j]=-inf;if(dp[i][j]>c)dp[i][j]=c;}for(int i=x;i<=n;i++)for(int j=y;j<=m;j++){if(i==x&&j==y) continue;else if(i==x) dp[i][j]=dp[i][j-1]+mp[i][j];else if(j==y) dp[i][j]=dp[i-1][j]+mp[i][j];else dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j];if(dp[i][j]<=0)dp[i][j]=-inf;if(dp[i][j]>c)dp[i][j]=c;}for(int i=x;i<=n;i++)for(int j=y;j>=1;j--){if(i==x&&j==y) continue;else if(i==x) dp[i][j]=dp[i][j+1]+mp[i][j];else if(j==y) dp[i][j]=dp[i-1][j]+mp[i][j];else dp[i][j]=max(dp[i-1][j],dp[i][j+1])+mp[i][j];if(dp[i][j]<=0)dp[i][j]=-inf;if(dp[i][j]>c)dp[i][j]=c;}for(int i=x;i>=1;i--)for(int j=y;j<=m;j++){if(i==x&&j==y) continue;else if(i==x) dp[i][j]=dp[i][j-1]+mp[i][j];else if(j==y) dp[i][j]=dp[i+1][j]+mp[i][j];else dp[i][j]=max(dp[i+1][j],dp[i][j-1])+mp[i][j];if(dp[i][j]<=0)dp[i][j]=-inf;if(dp[i][j]>c)dp[i][j]=c;}int k=max(max(dp[1][1],dp[n][m]),max(dp[1][m],dp[n][1]));if(k<0) cout<<"-1"<<endl;else cout<<k<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的计蒜客 逃生+动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。