ZCMU--1492: Problem D(C语言)

Description

Chieh最近在网上看到蓝翔非常火热。不知为什么他想到了一个问题，有一个n*m的矩阵

每一个小块里有k个石头。。现在挖掘机在左上角，挖掘机非常强大。。可以放无限的石头

但是它只能往右或者往下移动，现在Chieh想知道最多的石头从左上角到右下角。

Input

T 组数 T<=100

n m  1<=n. m<=1000

n行m个数 为石头数量 0<=s<=1000

Output

对于每组测试数据，输出对应的答案。

Sample Input

2

1  1

1

4  3

1  3  4

11  32  4

11  32  11

44  21  41

Sample Output

1

138

解析：题干说只能向右或者向下，因此f[ i ][ j ]只能从f[ i ][ j-1 ]或者f[ i-1 ][ j ]，也就是左边过来或者上方下来，对于f[ i ][ j ]，我们每次贪心选取max( f[ i ][ j-1 ]，f[ i-1 ][ j ] )再加上f[ i ][ j ]自己就是从左上到( i , j )位置的最大石子数。

 

#include <stdio.h>
#include <string.h>
int f[1005][1005]={0};
int max(int a,int b){	//max函数
	if(a>=b) return a;
	return b;
}
int main()
{
	int t,i,n,m,j;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){
			for(j=1;j<=m;j++){
				scanf("%d",&f[i][j]);
				f[i][j]=f[i][j]+max(f[i][j-1],f[i-1][j]);//选取左边和上面中最大的一方
			}
		}
		printf("%d\n",f[n][m]);
		memset(f,0,sizeof(f));    //记得初始化0，不然会有残留，导致下一组数据出现错误
	}
	return 0;
}