nyoj 712 探 尋 寶 藏（雙線dp 第六屆河南省程序設計大賽）

探 尋 寶 藏

傳說HMH大沙漠中有一個M*N迷宮，裡面藏有許多寶物。某天，Dr.Kong找到了迷宮的地圖，他發現迷宮內處處有寶物，最珍貴的寶物就藏在右下角，迷宮的進出口在左上角。當然，迷宮中的通路不是平坦的，到處都是陷阱。Dr.Kong決定讓他的機器人卡多去探險。

但機器人卡多從左上角走到右下角時，只會向下走或者向右走。從右下角往回走到左上角時，只會向上走或者向左走，而且卡多不走回頭路。（即：一個點最多經過一次）。當然卡多順手也拿走沿路的每個寶物。

2 2 3 0 10 10 10 10 80 3 3 0 3 9 2 8 5 5 7 100

120 134

這道題和以往我們做的dp不同之處就在於 是一去一回

加入只有去 我們可以 用動態規劃方程 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+map[i][j].

而這道題去了又回來 我們可以理解為兩個人同時從左上角去 不過不走相同的路

如果兩個人不走相同的路 那麼這兩個人必須不在相同的列或者行 又因為 兩個人走的步數完全相同

所以我們可以通過一個人走的步數得到另外一個人走的步數

我們可以通過一個四維的數組來保存

於是這個時候的動態規劃方程

附上代碼：

 
#include 
#include 
#include 
using namespace std;
int map[55][55];	
int dp[55][55][55][55];
int main()
{

	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		int n,m;
		memset(dp,0,sizeof(dp));
		memset(map,0,sizeof(map));
		scanf("%d %d",&m,&n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				for(int k=i+1;k<=m;k++)
				{
					int l=i+j-k;
					if(l<0||l>n)
					break;
					dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),
					max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l];
				}
		printf("%d\n",max(max(dp[m][n-1][m-1][n],dp[m][n-1][m][n-1]),
		max(dp[m-1][n][m-1][n],dp[m-1][n][m][n-1]))+map[m][n]);
	}
}         

dp[k][i][j] 其中k為當前走的步數 i為第一個人的行左邊 j為第二個人的行坐標

又因為我所建的圖左上角坐標為（1,1） 所以從左上角到右下角需要的最少步數為m+n-2

這個時候的動態轉移方程為

ac代碼：

 
#include 
#include 
#include 
using namespace std;
int map[55][55];	
int dp[110][55][55];
int main()
{

	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		int n,m;
		memset(dp,0,sizeof(dp));
		memset(map,0,sizeof(map));
		scanf("%d %d",&m,&n);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
		int step=m+n-2;
		
		for(int i=1;i<=m;i++)
			for(int j=i+1;j<=m;j++)	
			for(int k=1;k=i&&k+2>=j)
					{
						dp[k][i][j]=max(max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]),
						max(dp[k-1][i][j],dp[k-1][i][j-1]))+map[i][k-i+2]+map[j][k-j+2];
					}
					
				}
		printf("%d\n",max(dp[step-1][m][m-1],dp[step-1][m-1][m])+map[m][n]);
	}
	return 0;
}         

描述 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)
所有數據都是整數。 數據之間有一個空格。

輸出對於每組測試數據，輸出一行：機器人卡多攜帶出最多價值的寶物數

樣例輸入

樣例輸出

 dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]), 29.max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l];

由於四維數組占用的空間特別大 又因為在這道題中兩個人走的步數完全相同 也就是i+j=k+l 所以我們可以通過步數 轉換為3維的 dp[k][i][j]=max(max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]), 30.max(dp[k-1][i][j],dp[k-1][i][j-1]))+map[i][k-i+2]+map[j][k-j+2];