POJ 1050 To the Max -- 动态规划

时间:2022-09-07 12:01:50

题目地址:http://poj.org/problem?id=1050

Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle.
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

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace
(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

Output the sum of the maximal sub-rectangle.

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 -- 动态规划的更多相关文章

  1. &lbrack;ACM&lowbar;动态规划&rsqb; POJ 1050 To the Max &lpar; 动态规划 二维 最大连续和 最大子矩阵)

    Description Given a two-dimensional array of positive and negative integers, a sub-rectangle is any ...

  2. POJ 1050 To the Max 最大子矩阵和(二维的最大字段和)

    传送门: http://poj.org/problem?id=1050 To the Max Time Limit: 1000MS   Memory Limit: 10000K Total Submi ...

  3. poj 1050 To the Max&lpar;最大子矩阵之和&rpar;

    http://poj.org/problem?id=1050 我们已经知道求最大子段和的dp算法 参考here  也可参考编程之美有关最大子矩阵和部分. 然后将这个扩大到二维就是这道题.顺便说一下,有 ...

  4. POJ 1050 To the Max 暴力&comma;基础知识 难度&colon;0

    http://poj.org/problem?id=1050 设sum[i][j]为从(1,1)到(i,j)的矩形中所有数字之和 首先处理出sum[i][j],此时左上角为(x1,y1),右下角为(x ...

  5. poj 1050 To the Max &lpar;简单dp&rpar;

    题目链接:http://poj.org/problem?id=1050 #include<cstdio> #include<cstring> #include<iostr ...

  6. poj - 1050 - To the Max(dp)

    题意:一个N * N的矩阵,求子矩阵的最大和(N <= 100, -127 <= 矩阵元素 <= 127). 题目链接:http://poj.org/problem?id=1050 ...

  7. poj 1050 To the Max&lpar;线性dp&rpar;

    题目链接:http://poj.org/problem?id=1050 思路分析: 该题目为经典的最大子矩阵和问题,属于线性dp问题:最大子矩阵为最大连续子段和的推广情况,最大连续子段和为一维问题,而 ...

  8. poj 1050 To the Max&lpar;最大子矩阵之和,基础DP题&rpar;

    To the Max Time Limit: 1000MSMemory Limit: 10000K Total Submissions: 38573Accepted: 20350 Descriptio ...

  9. poj 1050 To the Max

    To the Max Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 45906   Accepted: 24276 Desc ...

随机推荐

  1. DropDownList 下拉框选择改变,促发事件和防全局刷新(记录)

    代码: <asp:ScriptManager ID="ScriptManager1" runat="server"> </asp:Script ...

  2. Leetcode 377&period; Combination Sum IV

    Given an integer array with all positive numbers and no duplicates, find the number of possible comb ...

  3. Loadrunner连接Mysql数据库

    1.库文件下载地址:http://files.cnblogs.com/files/xiaoxitest/MySQL_LoadRunner_libraries.zip 分别添加到Loadrunner b ...

  4. Python数据结构与算法--数据类型

    从数据类型开始 Python支持面向对象的编程范式,这意味着Python把数据看成解决问题的关键. 在Python中,类似其他的面向对象的编程语言, 我们定义一个类,用来描述数据是什么 (状态) 和数 ...

  5. W3C盒子与IE盒子模型

    盒模型: 内容(content).填充(padding).边界(margin). 边框(border) IE的content部分把 border 和 padding计算了进去 例:一个盒子的 marg ...

  6. apache POI 导出excel相关方法

    apache POI 操作excel无比强大.同时有操作word和ppt的接口. 下面讲解poi中常用方法. 1,设置列宽 HSSFSheet sheet = wb.getSheetAt(0); sh ...

  7. &lbrack;React&rsqb; React Router&colon; Router&comma; Route&comma; and Link

    In this lesson we'll take our first look at the most common components available to us in react-rout ...

  8. 数据库索引B-树和B&plus;树

    一开始学习数据结构的时候,主要学习的是数组,队列,链表,队列,栈,树这些数据结构,其中树主要学习二叉树,平衡二叉树,二叉搜索树等这些子节点最多只有两个的树结构.但是,当我们接触数据库的时候,你会发现数 ...

  9. oracle去掉字段全部空格进行模糊查询

    sql如下: select * from pwlp_law_person where replace(name,' ','') like replace('吕 刚',' ','');

  10. &lbrack;ovs&rsqb;&lbrack;dpdk&rsqb; ovs-dpdk 线程数,收包队列,core绑定

    http://docs.openvswitch.org/en/latest/intro/install/dpdk/?highlight=dpdk 绑定2,4,6, 8核 [root@vrouter1 ...