百练 OJ 2766 最大子矩阵

//ID: 百练 OJ 2766 最大子矩阵
//题目地址: http://poj.grids.cn/problem/2766
//My Name: Tanky_Woo
//My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习
//Website Link: http://www.cpply.com/
//My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛
//BBS Link:http://www.cppleyuan.com/
//My Blog:www.wutianqi.com
//豆瓣小组:http://www.douban.com/group/cppleyuan/
//QQ:17611904
//QQ群:C++奋斗乐园①群:19333724(满) ②群:23840480 (满)③群:17314377 ④群:23829384
//转载请写上本帖链接 www.cpply.com|www.cppleyuan.com|www.wutianqi.com
//及名称”Tanky Woo与ACM一起走过的日子”和“C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 //方法一
/*思想很经典,即利用求数组最长子段的函数。现在考虑如何利用这个函数,从第一行开始,到N行,遍历每种情况:
第i行到第j行上下元素相加,压缩成一个数组*/
#include <iostream>
using namespace std;
 
int N;
int aMatrix[101][101];
int aLine[101];
#define INF -10000000
 
int maxSubMatrix(int *line);
 
int main()
{
	//freopen("input_2766.txt", "r", stdin);
	int maxSum = INF;
	int i, j, k , h;
	scanf("%d", &N);
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			scanf("%d", &aMatrix[i][j]);
	for(k = 0; k < N; k++)
	{
		for(h = k; h < N; h++)
		{
			for(j = 0; j < N; j++)
				aLine[j] += aMatrix[h][j];
			int sum = maxSubMatrix(aLine);
			if(sum > maxSum)
				maxSum = sum;
		}
		memset(aLine, 0, sizeof(aLine));
 
 
	}
	printf("%d\n", maxSum);
	return 0;
}
 
 
 
int maxSubMatrix(int *line)  //求数组的最长子段
{
	int i;
	int b = line[0], sum = line[0];
	for(i = 1; i < N; i++)
	{
		if(sum > 0)     //这个地方应该是判断b是否大于0,我先写成了sum,结果测试了几组数据是对的,但其实是错的!
			b += line[i];
		else
			b = line[i];
 
		if(b > sum)
			sum = b;
	}
 
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 //方法二:
/*这题应该算用了DP吧。*/
 
#include<stdio.h>
#include<memory.h>
int a[102][102];
int b[102][102];
 
int main(){
 //1.两个坐标点就确定了一个矩阵,然后枚举所有的矩阵(直接枚举会超时)
 //2.先计算(0,0)(i.j)确定的矩阵的值b[i][j]
 //3.枚举所有矩阵,利用b[i][j]分割计算 
 int n,ma=0;
 scanf("%d",&n);
 for(int i=0;i<=n+1;i++){//设置边框
  a[0][i]=0;
  a[n+1][i]=0;
  a[i][0]=0;
  a[i][n+1]=0;
 }
 
 for(int i=1;i<=n;i++)//输入
  for(int j=1;j<=n;j++){
   scanf("%d",&a[i][j]);
   if(a[i][j]>ma)ma=a[i][j];
  }
 
 
 for(int i=0;i<=n;i++)        //求b[i][j]
  for(int j=0;j<=n;j++)
   for(int p=0;p<=i;p++)
    for(int q=0;q<=j;q++)
     b[i][j]+=a[p][q];
 int sum=0;
 for(int i=1;i<=n;i++)    //枚举矩阵
  for(int j=1;j<=n;j++)
   for(int p=i;p<=n;p++)
    for(int q=j;q<=n;q++){
     sum=0;
     sum=b[p][q]-b[p][j-1]-b[i-1][q]+b[i-1][j-1];
     if(sum>ma)ma=sum;
 
    }
 printf("%d",ma);
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《百练 OJ 2766 最大子矩阵》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注