首页 > 其他分享 >51nod 1051 最大子矩阵和

51nod 1051 最大子矩阵和

时间:2024-09-09 20:02:33浏览次数:11  
标签:1051 51nod ll 矩阵 int 505

51nod 1051 最大子矩阵和

可以用前缀和容斥优化到 \(O(n^4)\),但是不够进行如下图操作:

image

将每一列的数值都压缩到一维的数组上,就转换为求最大字段和问题,时间复杂度 \(O(n^3)\)。

看看代码就知道了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m; 
int a[505][505];
ll b[505];
 
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cin>>a[i][j];
		}
	}
	ll ans=INT_MIN;
	for(int l=1;l<=n;l++){
		memset(b,0,sizeof b);//起点变了,清零。
		for(int r=l;r<=n;r++){
			for(int k=1;k<=m;k++){//合并位一维数组
				b[k]+=a[r][k];
			}
			ll mx=INT_MIN;
			ll cmx=0; 
			for(int k=1;k<=m;k++){//最大字段和
				cmx=max(b[k],cmx+b[k]);
				mx=max(mx,cmx);
			}
			ans=max(ans,mx);
		}
	}
    if(ans<0){
    	cout<<0;
	}
	else{
		cout<<ans;
	}
    return 0;
}

标签:1051,51nod,ll,矩阵,int,505
From: https://www.cnblogs.com/sadlin/p/18405218

相关文章

  • 51nod 1243 排船的问题
    51nod1243排船的问题求最长绳子最短,考虑二分答案,判断时我们优先向左放,看是否能全放下。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,x,m;intpos[50005];intcheck(intmid){ intp=x;//偏差地图 intx2=x*2; intmx=m+x;//偏差地图 ......
  • 信息学奥赛初赛天天练-87-NOIP2014普及组-完善程序-矩阵、子矩阵、最大子矩阵和、前缀
    1完善程序最大子矩阵和给出m行n列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。输入第一行包含两个整数m和n,即矩阵的行数和列数。之后m行,每行n个整数,描述整个矩阵。程序最终输出最大的子矩阵和。(最后一空4分,其余3分,共16分)比如在如下这个矩阵中:440-2-7......
  • 短视频seo矩阵源码---MVC框架开发技术分享
    一.短视频矩阵源码数据库建立1.用户表(user):-用户ID(user_id)-用户名(username)-密码(password)-手机号(phone)-邮箱(email)2.账号表(account):二. MVC框架开发技术分享MVC(模型-视图-控制器)是一种常见的软件架构模式,用于将应用程序的不同部分分离开来,以实现更好的可维护性和......
  • 短视频矩阵系统源码----SaaS化技术开发方案
    一.短视频矩阵系统介绍短视频矩阵系统是一种用来管理和展示短视频的系统。它可以帮助用户快速浏览和观看大量的短视频内容,提供了多种功能和工具来帮助用户管理和优化短视频的播放体验。1.账号管理(覆盖抖音、快手、B站、视频号等平台)企业可将多平台多个账号进行统一授权管......
  • 51nod 1020 逆序排列
    51nod1020逆序排列学习笔记其实要预处理,但唐的我非要每次都求一遍。设状态为\(dp[i][j]\)选了i个数逆序对数为j的排序种类数。首先初始化\(dp[i][0]=1\)即没有逆序对,转移方程\(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+……+dp[i-1][j-i]\)这是显然的(放上这个数,会产生的......
  • 51nod 1296 有限制的排列
    题目链接学习链接设状态\(dp[i][j]\)表示整数\([1,i]\)满足要求的排列中,最后一个数选\(j\)的排列数。开一个数组记录他的状态:把前面已选好的序列中大于等于\(j\)的数都加一后再把\(j\)加到后面。#include<bits/stdc++.h>usingnamespacestd;#definelllong......
  • 51nod 1050 循环数组最大子段和
    51nod1050循环数组最大子段和虽然是板子题,两种做法,我们先写一种,另一个咕咕。因为是循环,所以分为两种,中间的和两边的,中间的直接dp求最大,两边的转化一下就是总的数字和减去中间的最小数字和。#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[500005]......
  • 《动手学深度学习》笔记3——矩阵求导
    李沐老师的讲解思路是先从数学概念引入,讲完以后再到代码实现:1.数学概念1.1标量导数1.2向量求导(梯度)分为四种情况:1.2.1标量y,关于向量x求导李沐老师这里先讲了y为标量,x为向量的情况,x是长度为1的列向量,关于列向量的导数(即梯度)是行向量,具体解释如下:在这个例子里, ......
  • 51nod 1791 合法括号子段
    51nod1791原题链接因为在括号串固定的情况下,括号的匹配是固定不变的。所以对左括号进行匹配,p[i]表示与i这个括号相匹配的括号的位置,易得到dp方程ans[i]=ans[p[i]+1]+1,然后再从后先前一遍求和即可。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconst......
  • 51nod 石子分配
    可以发现步数限制把数轴变为了环。环之间不可以交换,环内相邻两点可以交换,然后我们只需要对每个环操作,最后累加。对于环上的每个石子堆,我们需要将其石子数调整到均值\(avg\)。因此,我们首先计算每个堆石子相对于\(avg\)的偏差,即\(nowa[i]-avg\)。因为相邻节点不一定能凑齐......