问题 1445: [蓝桥杯][历届试题]最大子阵-白红宇的个人博客

问题 1445: [蓝桥杯][历届试题]最大子阵

发布日期：2021-05-14 16:48:47 浏览次数：14 分类：精选文章

本文共 762 字，大约阅读时间需要 2 分钟。

题目描述

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

其中，A的子矩阵指在A中行和列均连续的一块。

样例说明

取最后一列，和为10。

数据规模和约定

对于100%的数据，1< =n, m< =500，A中每个元素的绝对值不超过5000。

输入

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。

接下来n行，每行m个整数，表示矩阵A。

输出

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

样例输入

3 3

-1 -4 3

3 4 -1

-5 -2 8

样例输出

这道题其实是二维的最大字段和的问题，我们只需要把上面的每一列压缩下来，枚举每一行，二维变一维就好做了。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int N=510;int a[N][N];int sc[N];int n,m; int get_ans(int a[]){ int ans=0; int maxv=-1e9; int dp[N]; dp[0]=a[0]; for(int i=1;i
            
             >n>>m; int ans=-1e9; for(int i=0;i
             
              >a[i][j]; for(int i=0;i
              
               =0;j--) { for(int k=0;k

上一篇：蓝桥训练最小生成树kruscal

下一篇：蓝桥训练 dp 背包

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章