首页 > 编程语言 >广州C++信奥老师解一本通题 1260:1282:最大子矩阵

广州C++信奥老师解一本通题 1260:1282:最大子矩阵

时间:2024-09-26 10:23:17浏览次数:11  
标签:信奥 最大 1282 int 1260 矩阵 110 输入

 【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如,如下4 × 4的矩阵

0  -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

 

的最大子矩阵是

 9 2
-4 1
-1 8

 

这个子矩阵的大小是15。

【输入】

输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。

【输出】

输出最大子矩阵的大小。

【输入样例】

4
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

【输出样例】

15

 

#include <bits/stdc++.h>
using namespace std;
int b[110][110]; //存储第b[i][j]为 第i行前含自己的元素累加行
//b[2][j]-b[1][j] 即为原来a[2][i]的元素 b[3][j]-b[1][j] 即为2行到第3行的累加和 
int dp[110],ans=-0x3f3f3f3f,n;  //asn有负数,要设置为很小的负数  dp数组记录每列最大子段和 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>b[i][j];
			b[i][j]+=b[i-1][j];
		}
	for(int i=1;i<=n;i++) 
		for(int j=i;j<=n;j++)
		{
			memset(dp,0,sizeof(dp));  
			for(int k=1;k<=n;k++)
			{
				dp[k]=max( b[j][k]-b[i-1][k], dp[k-1]+ b[j][k]-b[i-1][k] );  //要i-1行。例如 i=1,j=1时 
				ans=max(ans,dp[k]);
			}
		}
	cout<<ans;
	return 0;
}

 

标签:信奥,最大,1282,int,1260,矩阵,110,输入
From: https://www.cnblogs.com/nanshaquxinaosai/p/18432950

相关文章

  • 广州C++信奥赛老师解一本通题 1389:亲戚
    ​ 【题目描述】若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的某个人所在家族的人数。规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。【输入】第一行:三个整数n,(n......
  • 南沙C++信奥老师解一本通题 1264:【例9.8】合唱队形
    ​ 【题目描述】N位同学站成一排,音乐老师要请其中的(N−K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设KK位同学从左到右依次编号为1,2,…,K1,2,…,K,他们的身高分别为T1,T2,…,TK,则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)你的任务是,......
  • 南沙C++信奥老师解一本通题 1281:最长上升子序列
    ​ 【题目描述】一个数的序列bibi,当b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...,aiK),这里1≤i1<i2<...<iK≤N。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列......
  • 打卡信奥刷题(784)用Scratch图形化工具信P6488[普及组/提高组] [COCI2010-2011#6] OKUPL
    [COCI2010-2011#6]OKUPLJANJE题目描述一场巨大的派对结束以后,有五家报纸刊登了参加这场派对的人数,然而这些报纸上的数字可能是错误的。现在你知道整个会场的面积是LL......
  • 南沙C++信奥老师解一本通题 1260:【例9.4】拦截导弹(Noip1999)
    ​【题目描述】某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦......
  • 打卡信奥刷题(780)用Scratch图形化工具信P6414[普及组/提高组] [COCI2014-2015#1] PROSJ
    [COCI2014-2015#1]PROSJEK题目描述有一个数列aaa,现在按照下列公式求出一个数列bb......
  • 南沙C++信奥老师解一本通题:1372:小明的账单
    ​ 【题目描述】小明在一次聚会中,不慎遗失了自己的钱包,在接下来的日子,面对小明的将是一系列的补卡手续和堆积的账单…在小明的百般恳求下,老板最终同意延缓账单的支付时间。可老板又提出,必须从目前还没有支付的所有账单中选出面额最大和最小的两张,并把他们付清。还没有支付的......
  • 南沙C++信奥老师解一本通题 1357:车厢调度(train)
    ​ 【题目描述】有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n≤1000),分别按照顺序编号为1,2,3,…,n。假定在进入车站前,每节车厢之间都不是连着的,并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任......
  • 南沙C++信奥老师解一本通题:1337:【例3-2】单词查找树
    ​【题目描述】在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都画出与单词列表所对应的单词查找树,其特点如下:1.根结点不包含字母,除根结点外每一个结点都仅包含一个大写英文字母;2.从根结点到某一结点,路径上经过的字母依次连起......
  • 打卡信奥刷题(774)用Scratch图形化工具信P5739[普及组/提高组] 【深基7.例7】计算阶乘
    【深基7.例7】计算阶乘题目描述求n!n!n!,也就是1×......