APIO2009 采油区域
标签：tps img include amp fine ++ 技术 矩阵 main
挺好玩的一题。
题目
题意：从 \(N*M\) 的矩阵中选出 \(3\) 个互不相交的 \(K*K\) 的正方形，使它们所包含数的和最大。
用上图的六种切法把大矩阵切开，则其中必有一种切法使选出的 \(3\) 个正方形分别在切出的 \(3\) 个部分里。
前缀和维护即可。
#include
#define max(a,b)((a)>(b)?(a):(b))
const int N=1502;
int n,m,k,a[N][N],b0[N][N],b1[N][N],b2[N][N],b3[N][N],c0[N],c1[N],ans,tmp;
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i=k;i--)for(int j=m;j>=k;j--)
a[i][j]-=a[i][j-k]-a[i-k][j-k]+a[i-k][j],
c0[i]=max(c0[i],a[i][j]),
c1[j]=max(c1[j],a[i][j]);
for(int i=k;i=k;j--)
b1[i][j]=max(max(b1[i-1][j],b1[i][j+1]),a[i][j]);
for(int i=n;i>=k;i--)for(int j=k;j=k;i--)for(int j=m;j>=k;j--)
b3[i][j]=max(max(b3[i+1][j],b3[i][j+1]),a[i][j]);
for(int i=k;i+k
APIO2009 采油区域
标签：tps img include amp fine ++ 技术 矩阵 main
原文地址：https://www.cnblogs.com/Camp-Nou/p/11816090.html
评论