2 条题解
-
4
赛时有幸想出正解,先说一下做法:
我们发现无论怎么放置这三个正方形,最后其分别所在区域一定可以划分成下面六种情况的其中一种:

下面暂且称一个L*L内的数字之和为取数和
虽然后面只提到了一次便不难想到
预处理出以每个节点为分割点将矩形分割为四个部分后每个部分内的最大取数和
注意:
- 1.用前缀和维护
- 2.细致使用下标@
由此以来每个节点便都对应了四个参数,
巧妙的利用这四个参数便可以处理出这六种情况下のans,再取个max,over~顺便送一个code:
#include<bits/stdc++.h> using namespace std; const int N=2077; int n,m,l; int a[N][N]; int sum[N][N]; int lu[N][N]; int ru[N][N]; int ld[N][N]; int rd[N][N]; int ans; int getsum(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];} void I_N_I_T(){ //预处理part for(int i=l;i<=n;i++){ for(int j=l;j<=m;j++){ lu[i][j]=max(lu[i-1][j],lu[i][j-1]); lu[i][j]=max(lu[i][j],a[i][j]); } } for(int i=n-l+1;i>=1;i--){ for(int j=l;j<=m;j++){ ld[i][j]=max(ld[i+1][j],ld[i][j-1]); ld[i][j]=max(ld[i][j],a[i+l-1][j]); } } for(int i=l;i<=n;i++){ for(int j=m-l+1;j>=1;j--){ ru[i][j]=max(ru[i-1][j],ru[i][j+1]); ru[i][j]=max(ru[i][j],a[i][j+l-1]); } } for(int i=n-l+1;i>=1;i--){ for(int j=m-l+1;j>=1;j--){ rd[i][j]=max(rd[i+1][j],rd[i][j+1]); rd[i][j]=max(rd[i][j],a[i+l-1][j+l-1]); } } } signed main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>m>>l; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } for(int i=l;i<=n;i++){ for(int j=l;j<=m;j++){ a[i][j]=getsum(i-l+1,j-l+1,i,j); //L*L的区间数字和 } } I_N_I_T(); //四种 2+1 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ans=max(ans,lu[i][j]+ru[i][j+1]+ld[i+1][m]); ans=max(ans,ru[i][j]+rd[i+1][j]+lu[n][j-1]); ans=max(ans,rd[i][j]+ld[i][j-1]+ru[i-1][1]); ans=max(ans,ld[i][j]+lu[i-1][j]+rd[1][j+1]); } } //两种 1+1+1 for(int i=l;i<=n;i++){ for(int j=l;j<=m;j++){ ans=max(ans,lu[i-l][m]+a[i][j]+rd[i+1][1]); ans=max(ans,ld[1][j-l]+a[i][j]+ru[n][j+1]); } } cout<<ans; //完结撒花 return 0; }题外话别看了赛后放榜,本人发现自己得了35分! 的好成绩,刺眼的Time Exceed如此鲜红,鲜红的Time Exceed如此刺眼,直到第二天上午才被告数据出锅,我的65pts啊呜呜
o(╥﹏╥)o
- 1
信息
- ID
- 46
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 133
- 已通过
- 11
- 上传者