hdu 1081 最大子矩阵和

Love The Way You Lie 2022-08-03 11:40 178阅读 0赞

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int maze[102][102];
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    int t;
                    scanf("%d",&t);
                    maze[i][j]=maze[i][j-1]+t; //每一行的前j列和
                }
            }
    
            int ans=-inf;
            for(int i=1;i<=n;i++)
            {
                for(int j=i;j<=n;j++)
                {
                    int sum=0;
                    for(int k=1;k<=n;k++)  //计算从第i列到第j列中最大子矩阵
                    {
                        sum+=maze[k][j]-maze[k][i-1];  
                        if(sum>ans)ans=sum;
                        if(sum<0)sum=0;
                    }
                }
            }
         
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关 java最大子矩阵

问题描述小明有一个大小为 � × � N×M 的矩阵, 可以理解为一个 � N 行 � M 列的二维数组。我们定义一个矩阵 �

男娘i/ 2024年03月26日 13:17/ 0 赞/ 80 阅读

相关 POJ 1050 最大子段和的延伸最大子矩阵

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。 j

野性酷女/ 2022年09月30日 03:46/ 0 赞/ 175 阅读

相关 hdu 1081 最大子矩阵和

include<map> include<vector> include<cstdio> include<iostream>

Love The Way You Lie/ 2022年08月03日 11:40/ 0 赞/ 179 阅读

相关 Q - Phalanx HDU - 2859——基础dp-最大对称子矩阵

Think: 1知识点：基础dp-最大对称子矩阵 2题意：给定一个矩阵，寻找一个最大对称子矩阵，当前题目最大对称子矩阵定义可理解为沿当前子矩阵的次对角线元素对称 3

超、凢脫俗/ 2022年06月10日 04:11/ 0 赞/ 147 阅读

相关 HDU 1505(动态规划-最大子矩阵)

问题描述: Bob is a strategy game programming specialist. In his new city building game the

墨蓝/ 2022年06月06日 01:19/ 0 赞/ 201 阅读

相关 HDU 2870(动态规划-最大子矩阵)

问题描述: Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change '

浅浅的花香味﹌/ 2022年06月05日 09:07/ 0 赞/ 206 阅读

相关 HDU 1081(动态规划-最大和子矩阵)

问题描述: Given a two-dimensional array of positive and negative integers, a sub-rectangle

秒速五厘米/ 2022年06月02日 07:07/ 0 赞/ 160 阅读

相关子矩阵的最大累加和

![Center][] //子矩阵的最大累加和 public class SubMatrixSum{ //找出最大的子矩阵

迈不过友情╰/ 2022年05月29日 01:11/ 0 赞/ 182 阅读

相关最大子矩阵最大子数组动态规划

最大子矩阵最大子数组动态规划最大子矩阵问题也是动态规划中经典的一道题目（感觉自己到目前为止接触到的只是动态规划的冰山一角，区间dp、数位dp… 还是要花时间

旧城等待，/ 2022年03月15日 04:16/ 0 赞/ 336 阅读

相关最大子序和——最大子矩阵

[LeetCode-最大子序和][LeetCode-] 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

清疚/ 2022年02月20日 05:52/ 0 赞/ 340 阅读