Skip to content

Instantly share code, notes, and snippets.

@Abreto
Created October 20, 2013 04:40
Show Gist options
  • Save Abreto/7065125 to your computer and use it in GitHub Desktop.
Save Abreto/7065125 to your computer and use it in GitHub Desktop.
Wikioi 1169 - 传递纸条.
/* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment