南郵 OJ 1237 收集樣本問題

收集樣本問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 41            測試通過 : 15 

比賽描述

機器人Rob在一個有n*n個方格的方形區域F 中收集樣本。（i,j）方格中樣本的價值為v(i,j)，如下圖所示。

Rob從方形區域F的左上角A點出發，向下或向右行走，直到右下角的B點，在走過的路上，收集方格中的樣本。Rob從A點到B 點共走2次，試找出Rob的2條行走路徑，使其取得的樣本總價值最大。

給定方形區域F中的樣本分布，程式設計計算Rob的2條行走路徑，使其取得的樣本總價值最大。

輸入

輸入第1行有1個正整數n，表示方形區域F有n*n個方格。接下來每行有3個整數，前2個表示方格位置，第3個數為該位置樣本價值。最後一行是3個0。

輸出

輸出計算的最大樣本總價值。

樣例輸入

8

2 3 13

2 6 6

3 5 7

4 4 14

5 2 21

5 6 4

6 3 15

7 2 14

0 0 0

樣例輸出

67

提示

undefined

題目來源

算法設計與實驗題解

//dp[x1][x2][sum]:兩條路徑同步走，分别走到map[x1][sum-x1]和map[x2][sum-x2],此時的最大樣本總價值
#include<stdio.h>
#define N 51
int dp[N][N][2*N];
int map[N][N];
int main(){
	int n,x1,x2,y1,y2,sum,max,temp;
	scanf("%d",&n);
	while(scanf("%d%d%d",&x1,&y1,&max)==3 && (x1||y1||max)){
		map[x1][y1] = max;
	}
	dp[1][1][2]=map[1][1];
	for(sum=3; sum<=2*n; sum++){
		for(x1=1; x1<=n; x1++){
			y1 = sum - x1;
			if(y1<1 || y1>n){
				continue;
			}
			for(x2=1;x2<=n;x2++){
				y2 = sum - x2;
				if(y2<1 || y2>n){
					continue;
				}
				max = 0;
				if(x1-1>0 && x2-1>0){
					if( (temp=dp[x1-1][x2-1][sum-1]) > max){
						max = temp;
					}
				}
				if(x1-1>0 && y2-1>0){
					if( (temp=dp[x1-1][x2][sum-1]) > max){
						max = temp;
					}
				}
				if(y1-1>0 && x2-1>0){
					if( (temp=dp[x1][x2-1][sum-1]) > max){
						max = temp;
					}
				}
				if(y1-1>0 && y2-1>0){
					if( (temp = dp[x1][x2][sum-1]) >max ){
						max = temp;
					}
				}
				if(x1==x2){
					dp[x1][x2][sum] = map[x1][y1] + max;
				}else{
					dp[x1][x2][sum] = map[x1][y1] + map[x2][y2] + max;
				}
			}
		}
	}
	printf("%d\n",dp[n][n][2*n]);
}