bzoj1177: [Apio2009]Oil

循环

题解：http://trinklee.blog.163.com/blog/static/238158060201482371229105/

刚开始把问题想的复杂了，想到了bzoj覆盖问题，但是俩者之间没有什么关系。那个是二分取得最大值。

本道题里，覆盖方式只可能出现题解里的6种。所以统计好前缀和就可以了。

各种变量要看清。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2000 + 10;

int n,m,k;
int a[maxn][maxn],s[maxn][maxn];
int tl[maxn][maxn],tr[maxn][maxn],bl[maxn][maxn],br[maxn][maxn]; //top-left,top-right,bottom-left,bottom-right
int res;

int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        scanf("%d",&a[i][j]);
        s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    } 
    
    for(int i=n;i>=k;i--)
    for(int j=m;j>=k;j--) s[i][j]-=(s[i-k][j]+s[i][j-k]-s[i-k][j-k]);
    
    //pre 4
    for(int i=k;i<=n;i++) 
    for(int j=k;j<=m;j++) tl[i][j]=max(s[i][j],max(tl[i-1][j],tl[i][j-1]));

    for(int i=k;i<=n;i++)
    for(int j=m;j>=k;j--) tr[i][j]=max(s[i][j],max(tr[i-1][j],tr[i][j+1]));

    for(int i=n;i>=k;i--)
    for(int j=k;j<=m;j++) bl[i][j]=max(s[i][j],max(bl[i+1][j],bl[i][j-1]));

    for(int i=n;i>=k;i--) 
    for(int j=k;j<=m;j++) br[i][j]=max(s[i][j],max(br[i+1][j],br[i][j+1]));
    
    //res 6
    for(int i=k;i<=n-k;i++)
    for(int j=k;j<=m-k;j++) res=max(res,tl[i][j]+tr[i][j+k]+bl[i+k][m]);
    for(int i=k;i<=n-k;i++)
    for(int j=k;j<=m-k;j++) res=max(res,tl[i][m]+bl[i+k][j]+br[i+k][j+k]);
    for(int i=k;i<=n-k;i++)
    for(int j=k;j<=m-k;j++) res=max(res,tl[n][j]+tr[i][j+k]+br[i+k][j+k]);
    for(int i=k;i<=n-k;i++)
    for(int j=k;j<=m-k;j++) res=max(res,tl[i][j]+bl[i+k][j]+tr[n][j+k]);
    for(int i=k;i<=n-k;i++)
    for(int j=k+k;j<=m-k;j++) res=max(res,s[i][j]+tl[n][j-k]+tr[n][j+k]);
    for(int i=k+k;i<=n-k;i++)
    for(int j=k;j<=m-k;j++) res=max(res,s[i][j]+tl[i-k][m]+bl[i+k][m]);
    printf("%d
",res);
    return 0;    
}