Wikioi 1169 - 传递纸条.

1169.c

/* Wikioi - Problem 1169 Passing notes. */
#include <stdio.h>
#define MAX(a,b)	( ((a)>(b))?(a):(b) )
#define MAX4(a,b,c,d)	(MAX(MAX((a),(b)),MAX((c),(d))))
#define MAXSIZE		52

int m = 0, n = 0;
int mat[MAXSIZE][MAXSIZE] = {{0}};
int f[MAXSIZE][MAXSIZE][MAXSIZE] = {{{0}}};

int
dp(int i, int j, int k)
{
	int *ans = &(f[i][j][k]);
	int l = i+j-k;
	
	if( *ans )
		return (*ans);
	if( i == k )
		return 0;
	if( i < 1 || j < 1 || k < 1 || l < 1 )
		return 0;
	if( 1 == i && 1 == j && 1 == k )
		return 0;
	return (*ans = (MAX4(dp(i-1,j,k-1),dp(i-1,j,k),dp(i,j-1,k-1),dp(i,j-1,k))+mat[i][j]+mat[k][l]));
}

int
main(void)
{
	int i = 0, j = 0;
	
	scanf("%d %d", &m, &n);
	for(i = 0;i < m;++i)
		for(j = 0;j < n;++j)
			scanf("%d", &(mat[i+1][j+1]));
	
	printf("%d\n", MAX(dp(m-1,n,m),dp(m,n-1,m-1)));
	return 0;
}