<center>

1013: 冒险游戏(risk_game)

时间限制: 2 Sec  内存限制:2048 MB
提交: 59  解决: 23
</center>

题目描述

河海组织一场冒险游戏,该游戏将场地分为N*M的方格,每个方格内均有一个关卡,要闯过每个关卡,都需要消耗一定数量的体力
游戏的起点为(1,1) 终点为(N,M),每通过一关,可以选择右方或下方的一个关卡,顺利通过终点则挑战成功,但在任何地方体力透支(体力值<0)则挑战失败
如果要通过挑战,在开始挑战时最少需要补充多少体力?

输入

第一行两个数,分别是n m,(1<= n,m <= 2000)
后面n行,每行m个非负数,表示每个关卡需要消耗的体力 (0<= a[i][j] <= 10000)

输出

一行,表示最小体力数

样例输入

2 2
1 2
3 4

样例输出

7

提示

共2条可选路径

1->2->4 7

1->3->4 8

来源

河海ACM前辈：姜鹏


思路：

一个二维的动态规划,给出一个矩阵，全是正数，要求从1,1 走到M,N，每次只能向下或向右，输出路径上点数字之和最小。状态转移方程：dp[i][j] = min{dp[i-1][j] , dp[i][j-1]} + a[i][j]。WA了几次，是因为inf开的太小了，之前还一直担心inf如果开的很大会爆掉，但是经过这几次的做题发现inf不会轻易爆掉的，反而有好几次是因为inf开的比较小而造成结果错误。另外数组也要开大一点。


代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

long long dp[2010][2010];
int a[2010][2010];

int min(int a,int b)
{
	return a<b?a:b;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{	
		for(int i=1;i<=n;i++)
		   for(int j=1;j<=m;j++)
		   {
		   	  scanf("%d",&a[i][j]);
		   }
		for(int i=2;i<=n;i++)dp[i][0]=1<<30;
		for(int i=2;i<=m;i++)dp[0][i]=1<<30;
		dp[0][0]=0;
		dp[0][1]=0;
		dp[1][0]=0;
		
		for(int i=1;i<=n;i++)
		   for(int j=1;j<=m;j++)
		   {
		   	  dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
		   }
		printf("%lld\n",dp[n][m]);	
	}
}