900
技術社區[雲棲]
NYOJ712-探尋寶藏
探 尋 寶 藏時間限製：1000 ms | 內存限製：65535 KB
難度：5
描述
傳說HMH大沙漠中有一個M*N迷宮，裏麵藏有許多寶物。某天，Dr.Kong找到了迷宮的地圖，他發現迷宮內處處有寶物，最珍貴的寶物就藏在右下角，迷宮的進出口在左上角。當然，迷宮中的通路不是平坦的，到處都是陷阱。Dr.Kong決定讓他的機器人卡多去探險。
但機器人卡多從左上角走到右下角時，隻會向下走或者向右走。從右下角往回走到左上角時，隻會向上走或者向左走，而且卡多不走回頭路。（即：一個點最多經過一次）。當然卡多順手也拿走沿路的每個寶物。
Dr.Kong希望他的機器人卡多盡量多地帶出寶物。請你編寫程序，幫助Dr.Kong計算一下，卡多最多能帶出多少寶物。
輸入
第一行： K 表示有多少組測試數據。
接下來對每組測試數據：
第1行: M N
第2~M+1行： Ai1 Ai2 ……AiN (i=1,…..,m)
【約束條件】
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
所有數據都是整數。 數據之間有一個空格。
輸出
對於每組測試數據，輸出一行：機器人卡多攜帶出最多價值的寶物數
樣例輸入
22 3
0 10 10
10 10 80
3 3
0 3 9
2 8 5
5 7 100
樣例輸出
120134
思路摘自：https://blog.csdn.net/sevenmit/article/details/8959923
這是雙進程DP問題，首先，假設出發點為A 終點為B 那麼，根據題目給出的條件，可以推出A->B的動態轉移方程為 dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + a[i][j]; 由於，同理可得B的情況，那麼，題目的意思是A->B 然後 B -> A我們可以假設同時從A點出發，得到兩條不同路徑，這個是一樣的效果。所以，我們可以得到一個動態轉移方程dp[i][j][p][q] = max(dp[i-1][j][p-1][q],dp[i-1][j][p][q],dp[i][j-1][p-1][q],dp[i][j-1][p][q-1]) 因為 每次隻能移動一步，即 i+1 或j+1 那麼 i+j是移動的步數 因為從A點開始移動的，經過相同的步數，肯定能得到i+j = p+q
還有一點要注意一下，這題與NYOJ 61是同類問題，但是，有一點細節要注意，最後終點的值也要算上，上麵的動態方程得到的值不包含兩個A 和 B的值，因為 A是起點，所以，他的值一般是0，所以，得到最後的結果應該是 int sum = max(dp[m-1][n][m-1][n],dp[m-1][n][m][n-1],dp[m][n-1][m-1][n],dp[m][n-1][m][n-1]) + a[m][n];
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[60][60];
int dp[60][60][60][60];
int max(int n,int m)
{
return n>m?n:m;
}
int main()
{
int i,j,T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
for(p=i+1;p<n;p++)
q=i+j-p;
if(q <= 0)
continue;
dp[i][j][p][q] = max(max(dp[i-1][j][p-1][q],dp[i][j-1][p][q-1]),
max(dp[i-1][j][p][q-1],dp[i][j-1][p-1][q])) + a[i][j] + a[p][q];
}
int sum = max(max(dp[m-1][n][m-1][n],dp[m-1][n][m][n-1]),
max(dp[m][n-1][m-1][n],dp[m][n-1][m][n-1]));
printf("%d\n",sum+a[m][n]);
}
return 0;
}
最後更新：2017-04-03 12:56:39