Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

给个O(N^4)的解法

Posted by ayxg at 2012-02-25 19:13:51 on Problem 1050
#include <stdio.h>

#define MAX 200

#define _row(i, n) ((i)/(n))
#define _col(i, n) ((i)%(n))
#define _indx(x, y) ((x)*(n) + (y))

int n;
char a[MAX * MAX];
int sum[MAX * MAX];

int main()
{
	int i, j, x, y, x1, y1, max, tmp;

	scanf("%d", &n);
	for (i = 0; i < n*n; ++i)
		scanf("%d", a + i);
	
	/* sum为每一个元素与第一元素组成矩形的所有元素之和 */
	sum[0] = a[0];
	for (i = 1; i < n; ++i)
		sum[i] = sum[i - 1] + a[i];
	for (i = n; i < n*n; ++i)
	{
		x = _row(i, n); y = _col(i, n);
		sum[i] = sum[_indx(x - 1, y)];	
		for (j = 0; j <= y; ++j)
			sum[i] += a[_indx(x, j)];
	}

	max = -127 * n * n;
	for (i = 0; i < n*n; ++i)
	{
		x = _row(i, n); y = _col(i, n);
		for (x1 = 0; x1 <= x; ++x1)
			for (y1 = 0; y1 <= y; ++y1)
			{
				tmp = sum[i];
				if (x1 > 0)
					tmp -= sum[_indx(x1 - 1, y)];
				if (y1 > 0)
					tmp -= sum[_indx(x, y1 - 1)];
				if (x1 > 0 && y1 > 0)
					tmp += sum[_indx(x1 - 1, y1 - 1)];
				if (tmp > max)
					max = tmp;
			}
	}

	printf("%d\n", max);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator