题目地址:http://poj.org/problem?id=1050
Description
In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
Input
(spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will
be in the range [-127,127].
Output
Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1 8 0 -2
Sample Output
15
时间复杂度为O(N^2*M^2)
#include <stdio.h>
#include <limits.h> //PS[i][j]等于以(1, 1), (1, j), (i, 1), (i, j)为顶点的矩形区域的元素之和
void Preproccess(int matrix[101][101], int PS[101][101], int N){
int i, j;
for (i=0; i<=N; ++i){
PS[0][i] = 0;
PS[i][0] = 0;
}
for (i=1; i<=N; ++i){
for (j=1; j<=N; ++j){
PS[i][j] = PS[i-1][j] + PS[i][j-1] - PS[i-1][j-1] + matrix[i][j];
}
}
} int main(void){
int N;
int matrix[101][101];
int PS[101][101];
int i, j;
int i_min, i_max;
int j_min, j_max;
int max, tmp; while (scanf ("%d", &N) != EOF){
for (i=1; i<=N; ++i)
for (j=1; j<=N; ++j)
scanf ("%d", &matrix[i][j]);
Preproccess(matrix, PS, N);
max = INT_MIN;
/*以(i_min, j_min), (i_max, j_min), (i_min, j_max), (i_max, j_max)为顶点的矩形区域的元素之和,
等于PS[i_max][j_max] - PS[i_min-1][j_max] - PS[i_max][j_min-1] + PS[i_min-1][j_min-1]
*/
for (i_min=1; i_min<=N; ++i_min){
for (i_max=i_min; i_max<=N; ++i_max){
for (j_min=1; j_min<=N; ++j_min){
for (j_max=j_min; j_max<=N; ++j_max){
tmp = PS[i_max][j_max] - PS[i_min-1][j_max] - PS[i_max][j_min-1] + PS[i_min-1][j_min-1];
if (tmp > max)
max = tmp;
}
}
}
}
printf ("%d\n", max);
} return 0;
}
时间复杂度为O(N*M*min(N, M))
#include <stdio.h>
#include <limits.h> //PS[i][j]等于以(1, 1), (1, j), (i, 1), (i, j)为顶点的矩形区域的元素之和
void Preproccess(int matrix[101][101], int PS[101][101], int N){
int i, j;
for (i=0; i<=N; ++i){
PS[0][i] = 0;
PS[i][0] = 0;
}
for (i=1; i<=N; ++i){
for (j=1; j<=N; ++j){
PS[i][j] = PS[i-1][j] + PS[i][j-1] - PS[i-1][j-1] + matrix[i][j];
}
}
} //BC(PS, a, c, i)表示在第a行和第c行之间的第i列的所有元素的和,可以通过“部分和”PS[i][j]在O(1)时间内计算出来。
int BC(int PS[101][101], int a, int c, int i){
return PS[c][i] - PS[a-1][i] - PS[c][i-1] + PS[a-1][i-1];
} int MaxSum (int matrix[101][101], int PS[101][101], int N){
int max = INT_MIN;
int a, c, i;
int Start, All;
for (a=1; a<=N; ++a){
for (c=a; c<=N; ++c){
Start = BC(PS, a, c, N);
All = BC(PS, a, c, N);
for (i=N-1; i>=1; --i){
if (Start < 0)
Start = 0;
Start += BC(PS, a, c, i);
if (Start > All)
All = Start;
}
if (All > max)
max = All;
}
}
return max;
} int main(void){
int N;
int matrix[101][101];
int PS[101][101];
int i, j; while (scanf ("%d", &N) != EOF){
for (i=1; i<=N; ++i)
for (j=1; j<=N; ++j)
scanf ("%d", &matrix[i][j]);
Preproccess(matrix, PS, N);
printf ("%d\n", MaxSum (matrix, PS, N));
} return 0;
}
HDOJ上相似的题目:http://acm.hdu.edu.cn/showproblem.php?pid=1559
九度OJ上相似的题目:http://ac.jobdu.com/problem.php?pid=1492
参考资料:编程之美
POJ 1050 To the Max -- 动态规划的更多相关文章
-
[ACM_动态规划] POJ 1050 To the Max ( 动态规划 二维 最大连续和 最大子矩阵)
Description Given a two-dimensional array of positive and negative integers, a sub-rectangle is any ...
-
POJ 1050 To the Max 最大子矩阵和(二维的最大字段和)
传送门: http://poj.org/problem?id=1050 To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submi ...
-
poj 1050 To the Max(最大子矩阵之和)
http://poj.org/problem?id=1050 我们已经知道求最大子段和的dp算法 参考here 也可参考编程之美有关最大子矩阵和部分. 然后将这个扩大到二维就是这道题.顺便说一下,有 ...
-
POJ 1050 To the Max 暴力,基础知识 难度:0
http://poj.org/problem?id=1050 设sum[i][j]为从(1,1)到(i,j)的矩形中所有数字之和 首先处理出sum[i][j],此时左上角为(x1,y1),右下角为(x ...
-
poj 1050 To the Max (简单dp)
题目链接:http://poj.org/problem?id=1050 #include<cstdio> #include<cstring> #include<iostr ...
-
poj - 1050 - To the Max(dp)
题意:一个N * N的矩阵,求子矩阵的最大和(N <= 100, -127 <= 矩阵元素 <= 127). 题目链接:http://poj.org/problem?id=1050 ...
-
poj 1050 To the Max(线性dp)
题目链接:http://poj.org/problem?id=1050 思路分析: 该题目为经典的最大子矩阵和问题,属于线性dp问题:最大子矩阵为最大连续子段和的推广情况,最大连续子段和为一维问题,而 ...
-
poj 1050 To the Max(最大子矩阵之和,基础DP题)
To the Max Time Limit: 1000MSMemory Limit: 10000K Total Submissions: 38573Accepted: 20350 Descriptio ...
-
poj 1050 To the Max
To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 45906 Accepted: 24276 Desc ...
随机推荐
-
DropDownList 下拉框选择改变,促发事件和防全局刷新(记录)
代码: <asp:ScriptManager ID="ScriptManager1" runat="server"> </asp:Script ...
-
Leetcode 377. Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...
-
Loadrunner连接Mysql数据库
1.库文件下载地址:http://files.cnblogs.com/files/xiaoxitest/MySQL_LoadRunner_libraries.zip 分别添加到Loadrunner b ...
-
Python数据结构与算法--数据类型
从数据类型开始 Python支持面向对象的编程范式,这意味着Python把数据看成解决问题的关键. 在Python中,类似其他的面向对象的编程语言, 我们定义一个类,用来描述数据是什么 (状态) 和数 ...
-
W3C盒子与IE盒子模型
盒模型: 内容(content).填充(padding).边界(margin). 边框(border) IE的content部分把 border 和 padding计算了进去 例:一个盒子的 marg ...
-
apache POI 导出excel相关方法
apache POI 操作excel无比强大.同时有操作word和ppt的接口. 下面讲解poi中常用方法. 1,设置列宽 HSSFSheet sheet = wb.getSheetAt(0); sh ...
-
[React] React Router: Router, Route, and Link
In this lesson we'll take our first look at the most common components available to us in react-rout ...
-
数据库索引B-树和B+树
一开始学习数据结构的时候,主要学习的是数组,队列,链表,队列,栈,树这些数据结构,其中树主要学习二叉树,平衡二叉树,二叉搜索树等这些子节点最多只有两个的树结构.但是,当我们接触数据库的时候,你会发现数 ...
-
oracle去掉字段全部空格进行模糊查询
sql如下: select * from pwlp_law_person where replace(name,' ','') like replace('吕 刚',' ','');
-
[ovs][dpdk] ovs-dpdk 线程数,收包队列,core绑定
http://docs.openvswitch.org/en/latest/intro/install/dpdk/?highlight=dpdk 绑定2,4,6, 8核 [root@vrouter1 ...