poj1050最大子矩阵和

poj1050最大子矩阵和

大家好,又见面了,我是全栈君。

这篇是看了别人的报告写的,就当是屡屡思路好了.

题目大意。给定一个n阶矩阵(方阵),每一个元素中存在一个数字.任务就是求出一个最大的子矩阵使得矩阵元素之间的和是最大的.

n=100;

1.矩阵A[m][n]的和能够直接 sum+=A[i][j] ( i = 0 to n-1 j=0 to n-1); 还能够求出第i列的和p[i],再将所在列加起来,(当然行是同理的).

2.因此所选的矩阵的行k能够枚举(0<=k<=n-1),此时能够现将列加起来,然后找到这些列中连续最大和就可以.这就是选出的矩阵最大和.

3.在全部矩阵中选出最大和的一个。

/*Source Code
Problem: 1050		User: 
Memory: 388K		Time: 32MS
Language: GCC		Result: Accepted

Source Code*/

    #include <stdio.h>
    int max(int a,int b){
            return a>b?

a:b; } int main(){ int i,j,k,n; int ans=-0xfffffff; int A[101][101]={0}; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%d",&A[i][j]); } } for(i=0;i<n;i++){ for(j=0;j<n;j++){ int add[101]={0},d[101]={0}; for(k=0;k<n;k++){ int l; for(l=i;l<=j;l++){ add[k]+=A[l][k]; } } d[0]=add[0]; ans=max(ans,d[0]); for(k=0;k<n;k++){ d[k]=d[k-1]>0?d[k-1]+add[k]:add[k]; ans=max(ans,d[k]); } } } printf("%d\n",ans); return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115265.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • tomcat配置教程idea_idea2019配置tomcat

    tomcat配置教程idea_idea2019配置tomcat1.打开idea,在项目运行列表下拉选择“editConfigurations”2.在打开的界面,点击“+”,再选择下面的TomcatServer下的local3.在打开的界面,第一行“Name”中填入tomcat的名称然后点击Configure…,在ApplicationServers界面,点击“+”,在TomcatServer配置界面选择要添加的tomcat…

    2022年10月30日
  • 列车调度问题PTA

    列车调度问题PTA7-20列车调度(25分)火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?输入格…

  • 程序员进大厂有多难_编程学完感觉啥也不会

    程序员进大厂有多难_编程学完感觉啥也不会冰河整理的这份并发编程核心技能,靠它进大厂,效果杠杠的,冰河强烈建议收藏!!

  • Django 安装_启动redis的命令

    Django 安装_启动redis的命令安装redis1.使用Homebrew安装Redisbrewinstallredis执行上述命令后出现以下内容,则成功安装Downloadfailed:https://mirrors.

  • SpringBoot线程池使用

    SpringBoot线程池使用一、线程池管理配置类@Configuration@EnableAsyncpublicclassExecutorConfig{privatestaticfinalLoggerlogger=LoggerFactory.getLogger(ExecutorConfig.class);@BeanpublicExecutorasyncTaskS…

  • (Python学习4)List对象

    1、PyListObject对象PyObject_VAR_HEAD中的obsize表示该list对象含有的元素个数,而allocated表示该list对象占用的内存空间。ob_item实际指向一个指

    2021年12月23日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号