P3625 采油区域-分类讨论
题意总结
在给定的 \(N*M\) 的矩形中，选出三个不重合的 \(k*k\) 的区域，使得权值和最大。
思路
第一眼想到了dp，类似于P1004的方格取数，开个三维取存选了那些点的最大值，但这里显然很难完成。于是ctj。
tj表示，很容易想到要分类讨论。想到的原因是一个区域内的最大的 \(k*k\) 易得。所以可以预处理出可能需要的块来拼出三块区域。总共分了6类：
然后预处理出这些块，最后枚举一下就好了。说实话，好恶心。
code
#include <bits/stdc++.h>
// #define int long long
using namespace std;
constexpr int maxn = 1.5e3+10;
constexpr int maxm = 1e5+10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;
bool Mst;int n,m,k,ans;
int mat[maxn][maxn],sum[maxn][maxn];
int lu[maxn][maxn],ld[maxn][maxn];
int ru[maxn][maxn],rd[maxn][maxn];
int col[maxn][maxn],row[maxn][maxn];int get_sum(int x1,int y1,int x2,int y2)
{return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];
}void init()
{for(int i=k;i<=n;++i){for(int j=k;j<=m;++j){lu[i][j]=max({lu[i][j-1],lu[i-1][j],get_sum(i-k+1,j-k+1,i,j)});}}for(int i=k;i<=n;++i){for(int j=m-k+1;j;--j){ru[i][j]=max({ru[i][j+1],ru[i-1][j],get_sum(i-k+1,j,i,j+k-1)});}}for(int i=n-k+1;i;--i){for(int j=k;j<=m;++j){ld[i][j]=max({ld[i][j+1],ld[i+1][j],get_sum(i,j-k+1,i+k-1,j)});}}for(int i=n-k+1;i;--i){for(int j=m-k+1;j;--j){rd[i][j]=max({rd[i][j+1],rd[i+1][j],get_sum(i,j,i+k-1,j+k-1)});}}for(int i=1;i<=n-k+1;++i){for(int j=1;j<=m-k+1;++j){row[i][i+k-1]=max(row[i][i+k-1],get_sum(i,j,i+k-1,j+k-1));}}for(int len=k+1;len<=n;++len){for(int i=1,j=i+len-1; j<=n ;++i,++j){row[i][j]=max(row[i][j-1],row[i+1][j]);}}for(int i=1;i<=m-k+1;++i){for(int j=1;j<=n-k+1;++j){col[i][i+k-1]=max(col[i][i+k-1],get_sum(j,i,j+k-1,i+k-1));}}for(int len=k+1;len<=m;++len){for(int i=1,j=i+len-1; j<=m ;++i,++j){col[i][j]=max(col[i][j-1],col[i+1][j]);}}
}bool Med;
signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endif // ONLINE_JUDGEcerr<<1.0*(&Med-&Mst)/1024/1024<<" M\n";scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){scanf("%d",&mat[i][j]);sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j];}}init();int ans=0;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){ans=max(ans,row[i+1][n]+lu[i][j]+ru[i][j+1]);ans=max(ans,row[1][i]+ld[i+1][j]+rd[i+1][j+1]);ans=max(ans,col[j+1][m]+lu[i][j]+ld[i+1][j]);ans=max(ans,col[1][j]+ru[i][j+1]+rd[i+1][j+1]);}}for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){ans=max(ans,row[1][i]+row[i+1][j]+row[j+1][n]);}}for(int i=1;i<=m;++i){for(int j=i+1;j<=m;++j){ans=max(ans,col[1][i]+col[i+1][j]+col[j+1][m]);}}printf("%d",ans);return 0;
}