| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
给个O(N^4)的解法#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator