SPOJ AMR11A Magic Grid（dp）

SPOJ AMR11AMagic Grid （题目链接）

题意：问从左上角走到右下角最少需要多少体力，体力小于等于0会死。

思路：dp。递推，倒着推，dp[i][j]表示i行j列最优值。dp[i][j]=max(1,min(dp[i][j+1]-mp[i][j+1],dp[i+1][j]-mp[i+1][j]));

启示：暴搜tle或mle而又不会剪枝时可以试试dp

/*************************************************************************
     File Name: A.cpp
     ID: obsolescence
     BLOG: http://blog.csdn.net/obsolescence
     LANG: C++ 
     Mail: [e-mail] 
     Created Time: 2016年07月20日 星期三 14时08分24秒
 ************************************************************************/
#include<bits/stdc++.h>
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define Abs(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))
#define ll long long
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x))
#define pb push_back
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int mp[N][N],dp[N][N];

int main(){
  int T,n,m,i,j;
  while(~scanf("%d",&T)){
    while(T--){
      scanf("%d%d",&n,&m);
      for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
          scanf("%d",&mp[i][j]);
      dp[n][m]=1;
      for(i=n-1;i>=1;--i){
        dp[i][m]=Max(1,dp[i+1][m]-mp[i+1][m]);
        //cout<<"dp["<<i<<"]["<<m<<"]="<<dp[i][m]<<endl;
      }
      for(j=m-1;j>=1;--j){
        dp[n][j]=Max(1,dp[n][j+1]-mp[n][j+1]);
        //cout<<"dp["<<n<<"]["<<j<<"]="<<dp[n][j]<<endl;
      }
      for(i=n-1;i>=1;--i)
        for(j=m-1;j>=1;--j)
          dp[i][j]=Max(1,Min(dp[i][j+1]-mp[i][j+1],dp[i+1][j]-mp[i+1][j]));
      printf("%d\n",dp[1][1]);
    }
  }
}