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