Max Sub-matrix

时间：2023-12-10 20:27:38

Max Sub-matrix

教练找的题目，目前样列过了

题意：找子矩阵的最大周长

思路：先离散每列，再枚举列（n*n），在当前枚举的两列之间求每行的和（n*n*n），但是开两个数组，一个包含两列上的元素  一个不包含，这样可以处理出前i行当前这两列上的元素和。  当前两列中每行元素和知道   两列上前i项和知道就可以找出最大值

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <stack>

 #include <vector>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <stdlib.h>

 #include <conio.h>

 #include <bits/stdc++.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 const int N=;

 const int MOD = 1e9+;

 #define LL long long

 void fre() {

     freopen("in.txt","r",stdin);

 }

 inline int r() {

     int x=,f=;char ch=getchar();

     while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;

 }

 int T,R ,s;

 struct node{

     int x,y,w;

     node(){}

     node(int xx,int yy,int ww):x(xx),y(yy),w(ww){}

     bool operator <(const node &a)const{

         return x<a.x;

     }

 }p[];

 int c;

 LL sum;

 int col[];

 LL l[],row[],row1[];

 void init(){

     R=r(),s=r();

     clc(col,);

     clc(l,);

     clc(row,);

     clc(row1,);

     c=;

     sum=;

     for(int i=;i<R;i++){

         for(int j=;j<s;j++){

             int x;

             x=r();

             if(x){

                 sum+=x;

                 p[c]=node(i,j,x);

                 col[c++]=j;

             }

         }

     }

 }

 LL work(){

     sort(p,p+c);

     sort(col,col+c);

     int n=unique(col,col+c)-col;

     if(n<=) return sum;

     LL ans=;

     for(int i=;i<n;i++){

         for(int j=i+;j<n;j++){

             int cmin=col[i],cmax=col[j];

             int cnt=;

             for(int k=;k<c;k++){

                 if(k==||p[k].x!=p[k-].x){

                     cnt++;

                     row[cnt]=row1[cnt]=;

                     l[cnt] = (cnt==)?:l[cnt-]+row1[cnt-]-row[cnt-];

                 }

                 int cnow=p[k].y;

                 int cost=p[k].w;

                 if(cnow>cmin&&cnow<cmax) row[cnt]+=cost;

                 if(cnow>=cmin&&cnow<=cmax) row1[cnt]+=cost;

             }

             // for(int i=1;i<=cnt;i++){

             //     printf("%d\n",l[i]);

             // }

             // cout<<endl;

             // getch();

             if(cnt<=) return sum;

             LL maxn=;

             for(int k=;k<=cnt;k++){

                 ans=max(ans,l[k]+row1[k]+maxn);

                 maxn=max(maxn,row[k]-l[k]);

             }

         }

     }

     return ans;

 }

 int main(){

     // fre();

     T=r();

     while(T--){

         init();

         LL ans=work();

         printf("%lld\n",ans);

     }

     return ;

 }

相关文章