Poj Solution 2078

http://poj.org/problem?id=2078

#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( "%dn", &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( "%dn", ans );
        
    }

    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *