1974.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1974 on 2006-01-09 at 21:29:23 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 8;
const int INF = 2000000;

int best, sum[MAX], less[MAX];
int m[MAX][2*MAX], n;

void DFS(int);

int main()
{
	int i, j;
	
	while(scanf("%d", &n) != EOF && n > 0) {
		memset(sum, 0, sizeof(sum));
		best = INF; less[n] = 0;
		for(i = 0; i < n; i++) {
			less[i] = INF;
			for(j = 0; j < n; j++) {
				scanf("%d", &m[i][j]);
				m[i][j+n] = m[i][j];
				less[i] = min(less[i], m[i][j]);
			}
		}
		for(i = n-2; i >= 0; i--) less[i] += less[i+1];
		DFS(0);
		printf("%d\n", best);
	}
	
	return 0;
}

void DFS(int o)
{
	int i, j;
	if(o == n) {
		int r = -INF;
		for(i = 0; i < n; i++) r = max(r, sum[i]);
		best = min(best, r);
	} else {
		for(i = 0; i < n; i++) {
			bool can = true;
			for(j = 0; j < n; j++) {
				sum[j] += m[o][i+j];
				if(sum[j] + less[o+1] >= best) can = false;
			}
			if(can) DFS(o+1);
			for(j = 0; j < n; j++) sum[j] -= m[o][i+j];
		}
	}
}