题目大意：输入一张整数表，求从左上角到右下角按每次向右，向下，或者是右下这种方式行走，到达右下角时能够收集的最大财富；

思路：很明显的dp，求到达右下角时最大，即每次到达的方格一定是他对应的左，上，左上三个方格中最大的，不断地化解子问题最终达到终点

代码如下：

#include<stdio.h>
#include<string.h>
int dp[1001][1001],map[1001][1001];
int max_(int a,int b,int c)
{
	if(a>b)
	{
		if(a>c)
			return a;
		else
			return c;
	}
	else if(b>c)
		return b;
	else
		return c;
}
int main()
{
	int i,j,n,m,t,c=0;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(dp,0,sizeof(dp));
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&map[i][j]);
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		dp[i][j]=max_(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+map[i][j];
		printf("Scenario #%d:\n%d\n\n",++c,dp[n][m]);
	}
	return 0;
}