2078.txt

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

#include "stdio.h"

int a[10][10], ans, n;
int k[10],sum[10];

void doit( int s )
{
	int i, maxv;
	
	if( s == n )
	{
		maxv = -1;
		for( i=0; i<n; i++ )
			if( sum[i] > maxv ) maxv = sum[i];
		ans = maxv;
		return;
	}

	for( k[s]=0; k[s]<n; k[s]++ )
	{
		for( i=0; i<n; i++ )
		{
			sum[i] += a[s][ (k[s]+i)%n ];
			if( sum[i] > ans ) break;
		}
	
		if( i == n )doit( s+1 );
	
		for( ; i>=0; i-- )
			sum[i] -= a[s][ (k[s]+i)%n ];
	}
}


int main()
{
	int cas, i, j;

	while( 1 )
	{
		scanf( "%d\n", &n );
		if( n < 0 ) break;

		for( i=0; i<n; i++ )
		for( j=0; j<n; j++ )
		scanf( "%d", &a[i][j] );
		
		ans = 999999;
		for( i=0; i<n; i++ )
		sum[i] = 0;
		
		doit( 0 );
	
		printf( "%d\n", ans );
		
	}

	return 0;
}