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 ;
}
05-08 08:16