pku2444.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 120 行

#include <stdio.h>
#include <string.h>
#define size 510
#define ONLINE
typedef __int64 LLN;

LLN v[size][size];
LLN sum[size][size];
int M, N;

LLN Abs(LLN x)
{
	return x > 0 ? x : -x;
}

LLN Calc(LLN a, LLN b, LLN c)
{
	LLN res;
	return res = Abs(a - b) + Abs(a - c) + Abs(b - c);
}

void Solve()
{
	int i, j;
	LLN ans, tmp, A, B, C, D;
	memset(sum, 0, sizeof(sum));
	for (i = 1; i <= M; i++)
	{
		for (j = 1; j <= N; j++)
		{
			scanf("%I64d", &v[i][j]);
		}
	}
	for (i = 1; i <= M; i++)
	{
		for (j = 1; j <= N; j++)
		{
			sum[i][j] = sum[i][j - 1] + v[i][j];
		}
	}
	for (j = 1; j <= N; j++)
	{
		for (i = 1; i <= M; i++)
		{
			sum[i][j] += sum[i - 1][j];
		}
	}
	ans = (LLN) 65535 * 500 * 500 * 10000;
	for (i = 1; i < M - 1; i++)
	{
		for (j = i + 1; j < M; j++)
		{
			A = sum[i][N];
			B = sum[j][N] - sum[i][N];
			C = sum[M][N] - A - B;
			tmp = Calc(A, B, C);
			if (tmp < ans)
			{
				ans = tmp;
			}
		}
	}
	for (i = 1; i < N; i++)
	{
		for (j = i + 1; j < N; j++)
		{
			A = sum[M][i];
			B = sum[M][j] - sum[M][i];
			C = sum[M][N] - A - B;
			tmp = Calc(A, B, C);
			if (tmp < ans)
			{
				ans = tmp;
			}
		}
	}
	for (i = 1; i < M; i++)
	{
		for (j = 1; j < N; j++)
		{
			A = sum[i][j];
			B = sum[i][N] - A;
			C = sum[M][j] - A;
			D = sum[M][N] - A - B - C;
			tmp = Calc(A + B, C, D);
			
			if (tmp < ans)
			{
				ans = tmp;
			}
			tmp = Calc(A + C, B, D);
			if (tmp < ans)
			{
				ans = tmp;
			}
			tmp = Calc(B + D, A, C);
			if (ans == -1 || tmp < ans)
			{
				ans = tmp;
			}
			tmp = Calc(C + D, B, A);
			if (tmp < ans)
			{
				ans = tmp;
			}
		}
	}
	printf("%I64d\n", ans);
}

int main()
{
	while (EOF != scanf("%d %d", &M, &N) && (M + N))
	{
		Solve();
	}
	return 0;
}