题目大意
给定一个(N imes M(N leq 50,M leq 20000))的矩阵，给定(Kleq M)，要求以每行的某个点为左上角选取一个(2 imes K)的子矩阵，使得所有选出的子矩阵覆盖的值之和最大，输出这个最大值。如下图。
题解
这道题的Easy版本和Hard版本唯一的区别就是(K)的大小不一样，Easy版本(K)是20，Hard版本(K)是20000。
容易想到dp，设(dp[i][j])表示考虑了前(i)行，且以第(i)行的第(j)个格子为右下角选取了一个(2 imes K)的矩阵时的最大价值。
那么(dp[i][j]=max(dp[i-1][k]-S))，(S)表示本次选的以((i,j))为右下角的矩形和上一次选的以((i-1,k))为右下角的矩形的相交部分的价值,最终的答案就是(min{dp[N][j]})。
容易想到，对于两个矩形没有相交的情况，可以维护(dp[i][j])的前缀最大值和后缀最大值，然后状态转移是(O(1))的。
对于两个矩形相交的情况，对于(Easy)版本，因为(K)只有20，我们可以去暴力维护。但对于Hard版本，复杂度太高。
对于(dp[i][j])，我们是固定了(i)，然后从从小到大枚举(j)去(dp)的。考虑(dp[i][j-1])和(dp[i][j])之间的关系。
(dp[i][j-1])选取的是左上角为((i-1,j-K))，右下角为((i,j-1))的矩形，(dp[i][j])选取的是左上角为((i-1,j-K+1))，右下角为((i,j))的矩形，相当于选取的矩形往右移动了1格。那么对于右下角在第(i-1)行([j-K,j-1])范围内的矩形，在当前选取的矩形往右移动一格时，其(dp)值要加上(Matrix[i-1][j-K])，对于右下角在第(i-1)行([j,j+K-1])范围内的矩形，在当前选取的矩形往右移动一格时，其(dp)值要减去(Matrix[i-1][j])。
即要维护区间加、区间最大值，可以用线段树做。时间复杂度(O(NMlogM))。
Codeforces 1304F1 Easy版代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define RG register int
#define LL long long
template<typename elemType>
inline void Read(elemType &T){
elemType X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
T=(w?-X:X);
}
int Matrix[53][20010],Sum[53][20010],dp[53][20010];
int Pre[53][20010],Suf[53][20010];
int N,M,K;
inline int Calc(int x,int y){
int Res=0;
for(RG j=max(y-K+1,K);j<=y;++j){
int temp=Sum[x][y]-Sum[x-2][y]-Sum[x][y-K]+Sum[x-2][y-K]
+dp[x-1][j]-(Sum[x-1][j]-Sum[x-1][y-K]-Sum[x-2][j]+Sum[x-2][y-K]);
Res=max(Res,temp);
}
for(RG j=y+1;j<=min(M,y+K-1);++j){
int temp=Sum[x][y]-Sum[x-2][y]-Sum[x][y-K]+Sum[x-2][y-K]
+dp[x-1][j]-(Sum[x-1][y]-Sum[x-1][j-K]-Sum[x-2][y]+Sum[x-2][j-K]);
Res=max(Res,temp);
}
return Res;
}
int main(){
Read(N);Read(M);Read(K);
for(RG i=1;i<=N;++i)
for(RG j=1;j<=M;++j)
Read(Matrix[N-i+2][j]);
for(RG i=1;i<=N+1;++i)
for(RG j=1;j<=M;++j)
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+Matrix[i][j];
for(RG i=K;i<=M;++i)
dp[2][i]=Sum[2][i]-Sum[0][i]-Sum[2][i-K]+Sum[0][i-K];
for(RG j=1;j<=M;++j){
Pre[2][j]=max(Pre[2][j-1],dp[2][j]);
Suf[2][M-j+1]=max(Suf[2][M-j+2],dp[2][M-j+1]);
}
for(RG i=3;i<=N+1;++i){
for(RG j=K;j<=M;++j){
dp[i][j]=Pre[i-1][j-K]+Sum[i][j]-Sum[i-2][j]-Sum[i][j-K]+Sum[i-2][j-K];
if(j+K<=M) dp[i][j]=max(dp[i][j],Suf[i-1][j+K]+Sum[i][j]-Sum[i-2][j]-Sum[i][j-K]+Sum[i-2][j-K]);
dp[i][j]=max(dp[i][j],Calc(i,j));
}
for(RG j=1;j<=M;++j){
Pre[i][j]=max(Pre[i][j-1],dp[i][j]);
Suf[i][M-j+1]=max(Suf[i][M-j+2],dp[i][M-j+1]);
}
}
int Ans=0;
for(RG i=K;i<=M;++i)
Ans=max(Ans,dp[N+1][i]);
printf("%d
",Ans);
return 0;
}
Codeforces 1304F2 Hard版代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define RG register int
#define LL long long
template<typename elemType>
inline void Read(elemType &T){
elemType X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
T=(w?-X:X);
}
int Matrix[53][20010],Sum[53][20010],dp[53][20010];
int Pre[53][20010],Suf[53][20010];
int N,M,K;
struct SegTreeNode{int Value,Lazytag;};
SegTreeNode SegTree[80010];
int Data[20010];
void Build_SegTree(int Root,int L,int R){
SegTree[Root].Lazytag=0;
if(L==R){SegTree[Root].Value=Data[L];return;}
int mid=(L+R)>>1;
Build_SegTree(Root<<1,L,mid);
Build_SegTree(Root<<1|1,mid+1,R);
SegTree[Root].Value=max(SegTree[Root<<1].Value,SegTree[Root<<1|1].Value);
return;
}
inline void Push_Down(int Root){
if(!SegTree[Root].Lazytag) return;
int Val=SegTree[Root].Lazytag;
SegTree[Root].Lazytag=0;
SegTree[Root<<1].Value+=Val;
SegTree[Root<<1].Lazytag+=Val;
SegTree[Root<<1|1].Value+=Val;
SegTree[Root<<1|1].Lazytag+=Val;
return;
}
void Update(int Root,int L,int R,int UL,int UR,int Add){
if(R<UL || UR<L) return;
if(UL<=L && R<=UR){
SegTree[Root].Value+=Add;
SegTree[Root].Lazytag+=Add;
return;
}
Push_Down(Root);
int mid=(L+R)>>1;
Update(Root<<1,L,mid,UL,UR,Add);
Update(Root<<1|1,mid+1,R,UL,UR,Add);
SegTree[Root].Value=max(SegTree[Root<<1].Value,SegTree[Root<<1|1].Value);
return;
}
int Query(int Root,int L,int R,int QL,int QR){
if(R<QL || QR<L) return 0;
if(QL<=L && R<=QR) return SegTree[Root].Value;
Push_Down(Root);
int mid=(L+R)>>1;
return max(Query(Root<<1,L,mid,QL,QR),Query(Root<<1|1,mid+1,R,QL,QR));
}
inline int Calc(int x,int y){
if(y!=K) Update(1,1,M,max(y-K,K),y-1,Matrix[x-1][y-K]);
if(y!=K) Update(1,1,M,y,min(y+K-1,M),-Matrix[x-1][y]);
return Query(1,1,M,y-K+1,min(y+K-1,M))+Sum[x][y]-Sum[x-2][y]-Sum[x][y-K]+Sum[x-2][y-K];
}
int main(){
Read(N);Read(M);Read(K);
for(RG i=1;i<=N;++i)
for(RG j=1;j<=M;++j)
Read(Matrix[N-i+2][j]);
for(RG i=1;i<=N+1;++i)
for(RG j=1;j<=M;++j)
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+Matrix[i][j];
for(RG i=K;i<=M;++i)
dp[2][i]=Sum[2][i]-Sum[0][i]-Sum[2][i-K]+Sum[0][i-K];
for(RG j=1;j<=M;++j){
Pre[2][j]=max(Pre[2][j-1],dp[2][j]);
Suf[2][M-j+1]=max(Suf[2][M-j+2],dp[2][M-j+1]);
if(K<=j && j<=2*K) Data[j]=dp[2][j]-(Sum[2][K]-Sum[2][j-K]-Sum[1][K]+Sum[1][j-K]);
else Data[j]=dp[2][j];
}
for(RG i=3;i<=N+1;++i){
Build_SegTree(1,1,M);
for(RG j=K;j<=M;++j){
dp[i][j]=Pre[i-1][j-K]+Sum[i][j]-Sum[i-2][j]-Sum[i][j-K]+Sum[i-2][j-K];
if(j+K<=M) dp[i][j]=max(dp[i][j],Suf[i-1][j+K]+Sum[i][j]-Sum[i-2][j]-Sum[i][j-K]+Sum[i-2][j-K]);
dp[i][j]=max(dp[i][j],Calc(i,j));
}
for(RG j=1;j<=M;++j){
Pre[i][j]=max(Pre[i][j-1],dp[i][j]);
Suf[i][M-j+1]=max(Suf[i][M-j+2],dp[i][M-j+1]);
if(K<=j && j<=2*K) Data[j]=dp[i][j]-(Sum[i][K]-Sum[i][j-K]-Sum[i-1][K]+Sum[i-1][j-K]);
else Data[j]=dp[i][j];
}
}
int Ans=0;
for(RG i=K;i<=M;++i)
Ans=max(Ans,dp[N+1][i]);
printf("%d
",Ans);
return 0;
}