now882I(差分)

|

题目链接

https://ac.nowcoder.com/acm/contest/882/I

题意

给定 $n\times m$ 的矩阵，选定两个子矩阵，使价值最大

价值定义为正好属于一个矩阵的元素的和

题解

这个题其实疯狂差分就可以了。。

首先把两个子矩阵没交的情况判了。。

然后考虑交的情况，我们在行上划四条线，表示两个矩阵选定的行，而且这个行上的区间有交

其次考虑列，列上同样要划四条线，不过我们可以不断求前缀，这样能够保证 $O(m)$ 的复杂度

这四个列也要求有交，然后再图上画一下这些列之后写一下价值的表达式就可以了。。

有个坑点是有包含的情况，需要考虑。。（感谢汪聚聚提供对拍




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include<assert.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,double>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define NM 55
#define nm 200005
const double eps=1e-4;
#define ll long long
using namespace std;
const ll inf=1e18;
char rc(){
    static char buf[10000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
ll read(){
    ll x=0,f=1;char ch=rc();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=rc();}
    while(isdigit(ch))x=x*10+ch-'0',ch=rc();
    return x*f;
}
void rd(char *x){
    char c=rc();
    while (isspace(c)) c=rc();
    while (!isspace(c)) *(x++)=c,c=rc();
    *x=0;
}
  
  
  
  
int n,m;
ll a[NM][NM],b[NM][NM],c[NM],d[NM],pre[NM][NM][NM],ans;
  
int main(){
    n=read();m=read();
    inc(i,1,n)inc(j,1,m)a[i][j]=read();
    inc(i,1,n)inc(j,1,m)b[i][j]=b[i-1][j]+a[i][j];
    inc(i,1,n)inc(j,i,n){
    ll t=0,s=0;
    inc(k,1,m)t=max(t+b[j][k]-b[i-1][k],0ll),s=max(s,t);
    c[i]=max(c[i],s);d[j]=max(d[j],s);
    }
    dec(i,n,1)c[i]=max(c[i],c[i+1]);
    inc(i,1,n)d[i]=max(d[i],d[i-1]);
    inc(i,1,n)ans=max(ans,d[i-1]+c[i]);
    inc(i,1,n)inc(j,1,m)b[i][j]=b[i][j-1]+a[i][j];
    mem(c);mem(d);
    inc(i,1,m)inc(j,i,m){
    ll t=0,s=0;
    inc(k,1,n)t=max(t+b[k][j]-b[k][i-1],0ll),s=max(s,t);
    c[i]=max(c[i],s);d[j]=max(d[j],s);
    }
    inc(i,1,n)d[i]=max(d[i],d[i-1]);
    dec(i,n,1)c[i]=max(c[i],c[i+1]);
    inc(i,1,n)ans=max(ans,d[i-1]+c[i]);
    inc(i,1,n)inc(j,1,m)b[i][j]=b[i-1][j]+a[i][j];
    inc(i,1,n)inc(j,1,n)inc(k,1,m)pre[i][j][k]+=pre[i][j][k-1]+b[j][k]-b[i-1][k];
    inc(_i,1,n)inc(_j,_i,n)inc(_k,1,_j)inc(_v,max(_k,_i),n){
    int l=max(_i,_k),r=min(_j,_v);
    ll*a=pre[_i][_j],*b=pre[_k][_v],*c=pre[l][r];
    inc(i,1,m)d[i]=max(d[i-1],-a[i-1]);//i
    inc(i,1,m)d[i]=max(d[i-1],d[i]-b[i-1]+2*c[i-1]);//k
    inc(i,1,m)d[i]=max(d[i-1],d[i]+a[i]-2*c[i]);//j
    inc(i,1,m)d[i]=max(d[i-1],d[i]+b[i]);//v
    ans=max(ans,d[m]);
    inc(i,1,m)d[i]=max(d[i-1],-a[i-1]);//i
    inc(i,1,m)d[i]=max(d[i-1],d[i]-b[i-1]+2*c[i-1]);//k
    inc(i,1,m)d[i]=max(d[i-1],d[i]+b[i]-2*c[i]);//v
    inc(i,1,m)d[i]=max(d[i-1],d[i]+a[i]);//j
    ans=max(ans,d[m]);
    }
    printf("%lld\n",ans);
    return 0;
}