2014百度の星資格試合1004:Labyrinth(DP)

Labyrinth
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1507    Accepted Submission(s): 520
Problem Description
度度度熊は探検が好きな熊で、偶然m*n行列の迷宮に落ちた.この迷宮は行列の左上角の最初の四角い格子からしか歩けない.右上角の最初の格子まで歩いてこそ迷宮を出ることができる.毎回1格しか歩けないし、上から下へ右へ行くしかない.以前歩いたことがない格子は、それぞれの格子の中に金貨がある.(正か負か、強盗が道を塞いで強盗に遭う可能性があります.
度度度熊は金貨を負にすることができて、強盗に借金を書く必要があります)、度度熊は最初は金貨の数を0にして、度熊が迷宮を出たときに最も多くの金貨を持っていますか?
 
 
Input
入力された最初の行は整数T(T<200)であり、Tグループのデータが共有されていることを示す.
各データ群の最初の行には、2つの正の整数m,n(m<=100,n<=100)が入力される.次のm行は、各行のn個の整数であり、それぞれ対応する格子で得られる金貨の数を表し、各整数は−100以上100以下である.
 
 
Output
各グループのデータについては、まず個別の行「Case#?:」、疑問符に現在のデータグループ数を記入し、グループ数は1から計算します.
各グループのテストデータは1行出力され、整数が出力され、最適な打法に基づいて右上隅に行くと得られる最大金貨の数を表します.
 
 
Sample Input
2
3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90
2 2
1 1
1 1
 
 
Sample Output
Case #1:
18
Case #2:
4
 
DP問題.
最初はDFSでやっていたので、思い切ってタイムアウト.討論版を見てやっとDPが必要だと気づき、その時はしおれていたが、後にネット上の問題解を調べて、DPでこの問題を解く方法が分かった.DPに対する理解はもっと深くなった.以下は構想である.
構想:この問題の構想は1列の各格子の最大金貨数を確定することである.まず第1列の最大金貨数を確定し、下へ行くしかないのでよく求める.その後、各列の各格子の最大金貨数は前の列から求めることができる.
例えばdp[i][j](dp[]]の意味はこの位置まで歩いた最大金貨数)を要求すると、前の列からこの格子まで3種類の歩き方がある.
1、その左側の格子、すなわちa[i][j-1]は、直接右に1つの格子を歩く.
2、a[i][j-1]の上のすべての格子は、まず右に1つの格子を歩いて、それから下に向かってa[i][j]の位置まで歩くことができます.
3、a[i][j-1]の下のすべての格子は、まず右に1つの格子を歩いてから、a[i][j]の位置まで上へまっすぐ行くことができます.
上記のすべてのパスを巡回する過程で最大値を記録する必要があり、最後にこの値がdp[i][j]の値である.
このことから,この位置の各経路を決定するにはm回の遍歴が必要であり,各列の各格子のdp[][]値を決定する必要があるため,このアルゴリズムの時間的複雑度はO(n*m)であることがわかる.
*m).
コード:

 1 #include <iostream>

 2 #include <stdio.h>

 3 using namespace std;  4 #define inf 0x7fffffff

 5 int a[110][110];  6 int dp[110][110];    //              

 7 int m,n;  8 void DP()  9 { 10     int i,j,k; 11     dp[1][1] = a[1][1]; 12     for(i=2;i<=m;i++)    //      

13         dp[i][1] = dp[i-1][1] + a[i][1]; 14     for(i=2;i<=n;i++){    //    a[][i]

15         for(j=1;j<=m;j++){    //          a[j][i] 16             //           。 17             //1.             。 18             //2.                          。 19             //3.                          。 20             //    ，       dp[j][i]     3       。                  。 21             //    a[j][i]      ，     a[j][i]     ，     

22             int t = dp[j][i-1] + a[j][i]; 23             if(t>dp[j][i]) 24                 dp[j][i] = t; 25             for(k=j-1;k>=1;k--){ 26                 //a[k][i-1] --> a[j][i]           

27                 t = t-dp[k+1][i-1]+dp[k][i-1]+a[k][i]; 28                 if(t>dp[j][i]) 29                     dp[j][i] = t; 30  } 31             t = dp[j][i-1] + a[j][i]; 32             for(k=j+1;k<=m;k++){ 33                 //a[k][i-1] --> a[j][i]           

34                 t = t-dp[k-1][i-1]+dp[k][i-1]+a[k][i]; 35                 if(t>dp[j][i]) 36                     dp[j][i] = t; 37  } 38  } 39  } 40 } 41 int main() 42 { 43     int i,j,Case,T; 44     scanf("%d",&T); 45     for(Case=1;Case<=T;Case++){ 46         scanf("%d%d",&m,&n); 47         for(i=1;i<=m;i++)    //    ，   dp[][]

48             for(j=1;j<=n;j++){ 49                 scanf("%d",&a[i][j]); 50                 dp[i][j] = -inf; 51  } 52         printf("Case #%d:
",Case); 53  DP(); 54         printf("%d
",dp[1][n]); 55  } 56     return 0; 57 }

 
タイムアウトしたDFSコードを貼り付けます.

 1 #include <iostream>

 2 #include <stdio.h>

 3 #include <string.h>

 4 using namespace std;  5 int Max;  6 int a[110][110];  7 bool isv[110][110];  8 int dx[3] = {1,-1,0};  9 int dy[3] = {0,0,1}; 10 int m,n; 11 bool judge(int x,int y) 12 { 13     if(x<1 || x>m || y<1 || y>n) 14         return true; 15     if(isv[x][y]) 16         return true; 17     return false; 18 } 19 void dfs(int x,int y,int money) 20 { 21     if(x==1 && y==n){ 22         if(money>Max) 23             Max=money; 24  } 25     int i; 26     for(i=0;i<3;i++){ 27         int nx = x+dx[i]; 28         int ny = y+dy[i]; 29         if(judge(nx,ny)) 30             continue; 31         //   

32         isv[nx][ny] = true; 33         dfs(nx,ny,money+a[nx][ny]); 34         isv[nx][ny] = false; 35  } 36 } 37 int main() 38 { 39     int i,j,Case,T; 40     scanf("%d",&T); 41     for(Case=1;Case<=T;Case++){ 42         scanf("%d%d",&m,&n); 43         for(i=1;i<=m;i++) 44             for(j=1;j<=n;j++) 45                 scanf("%d",&a[i][j]); 46         printf("Case #%d:
",Case); 47         Max=0; 48         memset(isv,0,sizeof(isv)); 49         isv[1][1] = true; 50         dfs(1,1,a[1][1]); 51         printf("%d
",Max); 52  } 53     return 0; 54 }

 
 
Freecode :  www.cnblogs.com/yym2013