题解 P3625 【[APIO2009]采油区域】

# 递推+前缀和 其实想清楚了本题就根本不难 首先考虑这题肯定要用到前缀和，那么怎么用就是一个问题了 一个矩形，分三块，有六种方法 如图  **分别在三个部分中找的k\*k面积最大的，加起来就是答案** 那么怎么表示这三个块中面积最大的呢？ 就需要记录对于每个点 它**左上，右上，左下，右下**的四个部分中，**最大的K\*K块的价值和** 这个样子： ```cpp int a[2000][2000],b[2000][2000],c[2000][2000],d[2000][2000]; //我的代码中a表示左上，b右上，c左下，d右下 ``` 怎么算这abcd四个二维数组呢： **一个s[][]二维数组记录，s[i][j]表示以i，j为右下角的K\*K正方形的石油储量之和** 那么递推可以推出a,b,c,d 得到abcd以后就分6个情况更新最大值，代码如下 ```cpp rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][m]+c[i+k][j]+d[i+k][j+k]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][j]+b[n][j+k]+c[i+k][j]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[n][j]+b[i][j+k]+d[i+k][j+k]); rep(i,k,n-k) rep(j,k+k,m-k) ans=max(ans,a[n][j-k]+b[n][j+k]+mp[i][j]); rep(i,k+k,n-k) rep(j,k,m-k) ans=max(ans,a[i-k][m]+c[i+k][m]+mp[i][j]); ``` 代码对应的情况如图  因为我在计算abcd的时候存的是正方形的右下角，所以+k才可以得到左上左下右上右下的值 自己画画图想想即可 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define FI for(int i=1;i<=n;i++) #define FJ for(int j=1;j<=m;j++) #define FDI for(int i=n;i>=k;i--) #define FDJ for(int j=m;j>=k;j--) #define FUI for(int i=k;i<=n;i++) #define FUJ for(int j=k;j<=m;j++) #define rep(i,x,y) for(int i=x;i<=y;i++) #define per(i,x,y) for(int i=x;i>=y;i--)//偷个懒 using namespace std; int mp[2000][2000]; int a[2000][2000],b[2000][2000],c[2000][2000],d[2000][2000]; int n,m,k; int main(){ //freopen("C:\\Users\\pc\\Desktop\\input.txt","r",stdin); scanf("%d%d%d",&n,&m,&k); int x; int cnt=1; FI FJ{ //printf("%d\n",cnt++); scanf("%d",&x); mp[i][j]=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]+x; } FDI FDJ mp[i][j]-=mp[i-k][j]+mp[i][j-k]-mp[i-k][j-k];//mp的意义是以i，j为右下角的K*K正方形的石油储量之和 FUI FUJ a[i][j]=max(mp[i][j],max(a[i-1][j],a[i][j-1])); FUI FDJ b[i][j]=max(mp[i][j],max(b[i-1][j],b[i][j+1])); FDI FUJ c[i][j]=max(mp[i][j],max(c[i+1][j],c[i][j-1])); FDI FDJ d[i][j]=max(mp[i][j],max(d[i+1][j],d[i][j+1]));//初始化abcd int ans=0; rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][m]+c[i+k][j]+d[i+k][j+k]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[i][j]+b[n][j+k]+c[i+k][j]); rep(i,k,n-k) rep(j,k,m-k) ans=max(ans,a[n][j]+b[i][j+k]+d[i+k][j+k]); rep(i,k,n-k) rep(j,k+k,m-k) ans=max(ans,a[n][j-k]+b[n][j+k]+mp[i][j]); rep(i,k+k,n-k) rep(j,k,m-k) ans=max(ans,a[i-k][m]+c[i+k][m]+mp[i][j]); //更新答案 printf("%d",ans); return 0; } ``` 广告 我的博客（里面更详细） [传送门](https://xianglujia.github.io/2017/08/11/ti\_APIO2009%20Oil/)