1050.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000

#if debug
    #define NMAX 10
#else
    #define NMAX 101
#endif
int N;
int a[NMAX][NMAX]={0};
int b[NMAX][NMAX][NMAX]={0};
long c[NMAX]={0};
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j,k,max=0,l;
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			scanf("%d",&a[i][j]);
		}
		
	}
	if(N==1)
	{
		printf("%d",a[0][0]);
		exit(0);
	}
	for(j=0;j<N;j++)
		b[0][j][0]=a[0][j];

	for(i=1;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			b[i][j][i]=a[i][j];
			for(k=0;k<i;k++)
			{
				b[i][j][k]=a[i][j]+b[i-1][j][k];
			}
		}
	}
	for(i=0;i<N;i++)
	{
		for(k=0;k<=i;k++)
		{
			c[0]=b[i][0][k];	
			
			for(j=1;j<N;j++)
			{
				
				c[j]=b[i][j][k]>b[i][j][k]+c[j-1]?b[i][j][k]:b[i][j][k]+c[j-1];
				max=max>c[j]?max:c[j];
			}
		}
	}
	printf("%d",max);

				
				
			

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}