参见《编程之美》2.14, 2.15 子数组和最大值(一维&二维)
转:POJ 2479/POJ 2593的拓展,从一维数组变成了二维矩阵,不过我们可以把情况模拟成一维的情况,在DP的基础上需要加上枚举。
题目要求求出给定的一个矩阵的和最大的子矩阵。
我们可以枚举第a行到第c行的情况(假设已经确定矩阵已经确定为最上面为第a行,最下面为第c行),那么只需要确定列的范围即可。我们可以把每一列都求和,这样会得到单独的一行,就可以直接求这一行的最大子段和即可。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define INF 1<<27
#define MAX_SIZE 101
int res=-INF;
int n;
int map[MAX_SIZE][MAX_SIZE];
int max(int a,int b){
return (a)>(b)?a:b;
}
void find_max(int top,int bottem){
//1. 退化为一维数组
int arr[MAX_SIZE];
memset(arr,0,sizeof(arr));
int i,j;
for(i=0;i<n;i++){
for(j=top;j<=bottem;j++){
arr[i]+=map[j][i];
}
}
//2. 求一位数组arr[0, ... , n-1]的和最大子数组的和
//*下面这种初始化方法使得如果全部为负数的话,最大值输出最大负数,而非0
int start[MAX_SIZE],all[MAX_SIZE];
all[n-1]=start[n-1]=arr[n-1];
for(i=n-2;i>=0;i--){
start[i]=max(arr[i],arr[i]+start[i+1]);
all[i]=max(start[i],all[i+1]);
}
if(all[0]>res) res=all[0];
}
void solve(){
//枚举最上面一行和最下面一行
int i,j;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
find_max(i,j);//DP:指定上下范围后,将矩形退化为一个数组,即求解数组的"和最大子数组"
}
}
}
int main(){
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&map[i][j]);
}
}
solve();
printf("%d",res);
system("pause");
return 0;
}
- 大小: 17.8 KB
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ3267-The Cow Lexicon
POJ3211--Washing Clothes
北大POJ2635-The Embarrassed Cryptographer 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码