Zcmu--1492: problem d (C language)

Description

Chieh Recently I saw Lan Xiang very hot on the Internet . Somehow he thought of a problem , There is one n*m Matrix

There are k A stone .. Now the excavator is in the upper left corner , Excavators are very powerful .. You can put unlimited stones

But it can only move to the right or down , Now? Chieh Want to know the most stones from the upper left corner to the lower right corner .

Input

T  Group number  T<=100

n m  1<=n. m<=1000

n That's ok m Number   Is the number of stones  0<=s<=1000

Output

For each group of test data , Output the corresponding answer .

Sample Input

2

1  1

1

4  3

1  3  4

11  32  4

11  32  11

44  21  41

Sample Output

1

138

analysis ： The title stem can only be right or down , therefore f[ i ][ j ] Only from f[ i ][ j-1 ] perhaps f[ i-1 ][ j ], That is to say, come to the left or come down from the top , about f[ i ][ j ], Every time we choose greedily max( f[ i ][ j-1 ],f[ i-1 ][ j ] ) Plus f[ i ][ j ] I am from top left to ( i , j ) The maximum number of stones at the location .

 

#include <stdio.h>
#include <string.h>
int f[1005][1005]={0};
int max(int a,int b){	//max function 
	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]);// Select the largest one on the left and above 
			}
		}
		printf("%d\n",f[n][m]);
		memset(f,0,sizeof(f));    // Remember to initialize 0, Otherwise there will be residues , Cause errors in the next set of data 
	}
	return 0;
}