Labyrinth

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 152????Accepted Submission(s): 76

Problem Description 度度熊是一只喜歡探險的熊，一次偶然落進了一個m*n矩陣的迷宮，該迷宮只能從矩陣左上角第一個方格開始走，只有走到右上角的第一個格子才算走出迷宮，每一次只能走一格，且只能向上向下向右走以前沒有走過的格子，每一個格子中都有一些金幣（或正或負，有可能遇到強盜攔路搶劫，度度熊身上金幣可以為負，需要給強盜寫欠條），度度熊剛開始時身上金幣數為0，問度度熊走出迷宮時候身上最多有多少金幣？

Input 輸入的第一行是一個整數T（T < 200），表示共有T組數據。
每組數據的第一行輸入兩個正整數m，n（m<=100，n<=100）。接下來的m行，每行n個整數，分別代表相應格子中能得到金幣的數量，每個整數都大于等于-100且小于等于100。

Output 對于每組數據，首先需要輸出單獨一行”Case #?:”，其中問號處應填入當前的數據組數，組數從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

Source 2014年百度之星程序設計大賽
– 資格賽

題目：http://acm.hdu.edu.cn/showproblem.php?pid=4826

思路：搜索的話，搜索空間太大，耗時太多。

DP：問題有最優子結構的性質。題目中說可以向右或者上下走，但是不能重復走，所以從左向右更新，但是只能從上往下或者從下往上單向更新。

代碼有點冗余，可能是因為不經常練習。

還有就是dp數組可以開成一維的。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 101
#define MIN -110000000
int dp[MAXN][MAXN] ;
int arr[MAXN][MAXN];
int main(){


? ? int N;
? ? cin >>N;
? ? int NN = N ;
? ? while (N-- > 0){
? ? ? ? int m , n ;
? ? ? ? cin>>m>>n;
? ? ? ? for(int i =0 ; i < m ; ++i){
? ? ? ? ? ? for(int j = 0 ; j < n ; ++j){
? ? ? ? ? ? ? ? cin>>arr[i][j];
? ? ? ? ? ? ? ? dp[i][j] = MIN;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for (int j = 0 ; j < n ;++j)
? ? ? ? {
? ? ? ? ? ? if (j!=0 && j != n-1){
? ? ? ? ? ? ? ? for (int i = 0 ; i < m ; ++i){


? ? ? ? ? ? ? ? ? ? dp[i][j] = dp[i][j-1]+arr[i][j];
? ? ? ? ? ? ? ? ? ? if(i != 0)
? ? ? ? ? ? ? ? ? ? dp[i][j] = max(dp[i][j] ,dp[i-1][j]+arr[i][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? int dptemp[MAXN];
? ? ? ? ? ? ? ? for (int i = m-1 ; i >= 0 ?; --i){
? ? ? ? ? ? ? ? ? ? dptemp[i] = dp[i][j-1]+arr[i][j];
? ? ? ? ? ? ? ? ? ?if (i!=m-1){
? ? ? ? ? ? ? ? ? ? dptemp[i] = max(dptemp[i] , dptemp[i+1]+arr[i][j]);
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? for (int i = 0 ; i < m ; ++i)
? ? ? ? ? ? ? ? ? ? dp[i][j] = max(dp[i][j] , dptemp[i]);
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? if (j==0){
? ? ? ? ? ? ? ? ? ? ? ? dp[0][0] =arr[0][0];
? ? ? ? ? ? ? ? ? ? ?for (int i = 0 ; i < m ; ++i){
? ? ? ? ? ? ? ? ? ? //dp[i][j] = max(dp[i][j-1]+arr[i][j];
? ? ? ? ? ? ? ? ? ? if(i != 0)
? ? ? ? ? ? ? ? ? ? dp[i][j] = max(dp[i][j] ,dp[i-1][j]+arr[i][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ?for (int i = m-1 ; i >= 0 ?; --i){
? ? ? ? ? ? ? ? ? ? dp[i][j] = max(dp[i][j-1]+arr[i][j],dp[i][j]);
? ? ? ? ? ? ? ? ? ? if(i != m-1)
? ? ? ? ? ? ? ? ? ? dp[i][j] = max(dp[i][j] ,dp[i+1][j]+arr[i][j]);
? ? ? ? ? ? ? ? }


? ? ? ? ? ? ? ? }


? ? ? ? ? ? }
? ? ? ? }
// ? ? ? ?for (int i = 0 ; i < m ; ++i){
// ? ? ? ? ? ?for(int j =0 ; j < n ; ++j){
// ? ? ? ? ? ? ? ?cout<<dp[i][j];
// ? ? ? ? ? ?if (j==n-1)
// ? ? ? ? ? ? ? ?cout<<endl;
// ? ? ? ? ? ?else
// ? ? ? ? ? ? ? ?cout<<" ";
// ? ? ? ? ? ?}
// ? ? ? ? ? ? ? }
? ? ? ? ?cout<<"Case #"<<NN-N<<":"<<endl;
? ? ? ? ?cout<<dp[0][n-1]<<endl;
? ? }


}

總結

以上是生活随笔為你收集整理的Labyrinth的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。