首页 > 其他分享 >最大子矩阵和问题 动态规划 51nod1051

最大子矩阵和问题 动态规划 51nod1051

时间:2023-06-02 18:36:16浏览次数:52  
标签:include 最大 子段 555 矩阵 51nod1051 int 动态





1051 最大子矩阵和



基准时间限制:2 秒 空间限制:131072 KB 分值: 40  难度:4级算法题




例如:3*3的矩阵:



-1 3 -1


2 -1 3


-3 1 2



和最大的子矩阵是:



3 -1


-1 3


1 2


Input


第1行:M和N,中间用空格隔开(2 <= M,N <= 500)。第2 - N + 1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9 <= M[i] <= 10^9)


Output


输出和的最大值。如果所有数都是负数,就输出0。


Input示例


3 3-1 3 -1 2 -1 3 -3 1 2


Output示例


7




分析:

还记得有一个最大子段和问题,是一维的一组数。

最大子段和 HDU杭电acm1003

而最大子矩阵和不过是它的一个二维模式。



1、先限定其中的一维,然后另一维就可以运用最大字段和解法了。


2、不妨先限定行,行被限制在区间【i ,  j】上


3、在行被限定的情况下,走列就行了,用最大字段和思想


代码解释:两层外循环限定行的区间,内循环按照最大子段和走一遍即可。



#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
ll arr[555][555];
ll dp[555][555];
int m,n;
int main()
{
	while(~scanf("%d%d",&m,&n))
	{
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%lld",&arr[i][j]);
				dp[i][j]=dp[i-1][j]+arr[i][j];
			}
		}
		ll ans=arr[1][1];
		for(int i=1;i<=n;i++)//行上端点 
			for(int j=i;j<=n;j++)//行下端点 
			{
				ll sum=0;
				for(int k=1;k<=m;k++)//遍历列
				{
					sum+=dp[j][k]-dp[i-1][k];//第k列,i~j行的和 
					if(sum<0)
						sum=0;
					if(ans<sum)
						ans=sum;
				}
			}
		printf("%lld\n",ans);
	}
	return 0;
 }








标签:include,最大,子段,555,矩阵,51nod1051,int,动态
From: https://blog.51cto.com/u_16125110/6404534

相关文章

  • 【C语言】动态内存管理函数的 深度解析 #是不是对数组不能变大变小而烦恼呢?学会动态内
    前言动态内存管理函数可以说很好用,但是有些小危险。所谓动态内存分配,就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不像数组等静态内存分配方法那样需要预先分配存储空间,而是由系统根据程序的需要即时分配,且分配的大小就是程序要求......
  • Python中动态导入对象importlib.import_module()的使用
    参考:https://blog.csdn.net/edward_zcl/article/details/88809212https://www.cnblogs.com/yhjoker/p/15969508.html经常在项目中碰到需要根据配置动态导入不同的类的方法进行运行,这时就要用动态函数import_module的使用方法假设项目目录结构如下: ......
  • 一图归纳三大种类矩阵范数:诱导范数,元素范数,Schatten范数,涵盖谱范数,2范数
    转载自:https://blog.csdn.net/qq_27261889/article/details/87902480......
  • 一文读懂责任分配矩阵,解决你80%的项目难题
    成功的项目管理取决于整个团队对角色和职责的理解,使用责任分配矩阵分配和定义角色是使项目保持在正轨并为成功做好准备的好方法。如果设计得当,责任分配矩阵能够促进项目的成功交付。一、什么是责任分配矩阵责任分配(RACI)矩阵是项目管理工具,用于定义和跟踪团队成员在项目中的角色......
  • 矩阵快速幂加速递推
    矩阵优化递推的思想在于把递推的层数化为矩阵的幂数,也就是说设计一个矩阵\(A\),使得\(A^n\)中的某个元素就是递推的第\(n\)项,即\(f_n\)。这么做就可以将\(O(n)\)的递推优化为\(O(\log_2n)\)的矩阵快速幂(矩阵\(A\)的行列数为常数,因此快速幂中的矩阵乘法复杂度为常数),本质......
  • Windows 下 JNA 调用动态链接库 dll
    1.创建动态链接库项目创建jnaTest项目下一步中填写项目名称和存储的目录;然后直接创建即可创建结果2.定义头文件#pragmaonce#ifndefJNA_TEST_H#defineJNA_TEST_H#ifdef__cplusplusextern"C"{#endif__declspec(dllexport)intadd(inta,intb);__declspec......
  • 2022-2023 春学期 矩阵与数值分析 C5 插值与逼近
    2022-2023春学期矩阵与数值分析C5插值与逼近C5插值与逼近原文5.1引言有n个插值节点,就有n插值条件,可以构造至多n-1次的插值函数需要考虑简单函数类的选取问题:如代数多项式,三角多项式,分段多项式,有理函数,样条函数等;存在唯一性问题;余项估计问题;收敛性问题等思......
  • kafka动态生产者
    packagecom.sunclouder.das.data.kafka.forward;importcn.hutool.core.util.StrUtil;importcn.hutool.json.JSONObject;importcn.hutool.json.JSONUtil;importcom.sunclouder.das.data.kafka.entity.ConfigEntity;importcom.sunclouder.das.data.kafka.entity.DasConfig......
  • 算法学习day39动态规划part02-62、63
    packageLeetCode.DPpart02;/***62.不同路径*一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。*机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。*问总共有多少条不同的路径?*示例:*输入......
  • 算法学习day41动态规划part03-343、96
    packageLeetCode.DPpart03;/***343.整数拆分*给定一个正整数n,将其拆分为k个正整数的和(k>=2),并使这些整数的乘积最大化。*返回你可以获得的最大乘积。*示例:*输入:n=2*输出:1*解释:2=1+1,1×1=1。**/publicclassIntegerBre......