POJ 1050 To the Max(最大矩阵)

技术文章 1年前 (2020) 完美者
482 0

标签:序列   col   set   play   div   org   print   c代码   +=   

题目链接:http://poj.org/problem?id=1050

 

和序列中无长度限制的最大子段和相同,如果当前的sum>0,那么它还有一定的价值,所以继续往上累加;如果当前sum<0,即sum不仅没有价值,反而会使后面的和更小,所以将sum重置为0为最优。

 

矩阵中维护每一列上的前缀和,枚举所选矩阵上限i,下限j,枚举列数k,重复上述过程,记录整个过程中的最大值即为答案。

 

AC代码:

技术图片

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=105;
 6 int n,maxx;
 7 int a[N][N];
 8 int main(){
 9     while(~scanf("%d",&n)){
10         memset(a,0,sizeof(a));
11         for(int i=1;i<=n;i++)
12         for(int j=1;j<=n;j++){
13             int t;
14             scanf("%d",&t);
15             a[i][j]=a[i-1][j]+t;
16         }
17         int sum=0;
18         maxx=0;
19         for(int i=1;i<=n;i++)
20         for(int j=i;j<=n;j++){
21             sum=0;
22             for(int k=1;k<=n;k++){
23                 int t=a[j][k]-a[i-1][k];
24                 sum+=t;
25                 if(sum<0) sum=0;
26                 if(sum>maxx) maxx=sum;
27             }
28         }
29         printf("%d\n",maxx);
30     }
31     return 0;
32 } 

AC代码

 

POJ 1050 To the Max(最大矩阵)

标签:序列   col   set   play   div   org   print   c代码   +=   

原文地址:https://www.cnblogs.com/New-ljx/p/13658244.html

版权声明:完美者 发表于 2020-09-17 23:21:37。
转载请注明:POJ 1050 To the Max(最大矩阵) | 完美导航

暂无评论

暂无评论...