首页 > 代码库 > POJ #1050 - To the Max
POJ #1050 - To the Max
Looks quite intuitive at the very first sight... I thought:
rect[x, y, w+1, h+1] = rect[x, y, w, h] + num[x + w + 1, y..y+h+1] + num[x..x+w+1, y+h+1] - num[x+w+1, y+h+1]
But that results in O(n^4) at least.
Reference: http://blog.csdn.net/hitwhylz/article/details/11848439. Lesson learnt: usually 2D issue can be converted to 1D problem to solve. Cool thought. And what is more important: decoding problem thoroughly and identify familiar pattern in disguise from it.
Here is my AC code:
// 1050// Ref: http://blog.csdn.net/hitwhylz/article/details/11848439#include <stdio.h>#define MAX_N 100#define Max(a, b) (a) > (b) ? (a) : (b)int max_sum_1D(int rowSum[MAX_N + 1], int n){ // dp[i] = max{a[i], dp[i-1] + a[i]} int ret = -2147483648; int dp[MAX_N + 1] = { 0 }; for (int k = 1; k <= n; k ++) { dp[k] = Max(rowSum[k], dp[k-1] + rowSum[k]); ret = Max(ret, dp[k]); } return ret;}int calc(int in[MAX_N + 1][MAX_N + 1], unsigned n){ int maxSum = -2147483648; for (int i = 1; i <= n; i++) { int rowSum[MAX_N + 1] = { 0 }; // for compact for (int j = i; j <= n; j++) // Row[i]..Row[j] { // Compact to 1D array, from row[i] to row[j] for each column for (int k = 1; k <= n; k++) { rowSum[k] += in[j][k]; } int tmp_sum = max_sum_1D(rowSum, n); maxSum = Max(tmp_sum, maxSum); } } return maxSum;}int main(){ int n; scanf("%d", &n); int in[MAX_N + 1][MAX_N + 1]; // Get input for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j++) { scanf("%d", &(in[i][j])); } // int ret = calc(in, n); printf("%d\n", ret); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。