BZOJ 1177 [Apio2009]Oil - 花式枚舉+亂搞

原來以為是什麼神題。。。結果。。。我的三觀。。。

大概是一道碼農題，所有三種情況的分類如下

（圖源Galaxies：http://www.cnblogs.com/galaxies/p/bzoj1177.html）

先字首和亂搞，然後計算一個點的四個方位的k*k的正方形中的總貢獻，左上右上左下右下分别為abcd，然後大力枚舉讨論每種情況就好了。。。

（真是一道練習寫數組下标的碼農好題）

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=;

int n,m,k,ans;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn],map[maxn][maxn],s[maxn][maxn];

int main()
{
    scanf("%d%d%d",&m,&n,&k);

    for(int i=;i<=m;i++)//二維字首和
        for(int j=;j<=n;j++)
            scanf("%d",&map[j][i]),
            map[j][i]=map[j][i]+map[j][i-]+map[j-][i]-map[j-][i-];

    for(int i=n;i>=k;i--)//計算(i,j)點左上角k*k矩形貢獻
        for(int j=m;j>=k;j--)
            s[i][j]=map[i][j]-map[i][j-k]-map[i-k][j]+map[i-k][j-k];

    //左上
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            a[i][j]=max(s[i][j],max(a[i-][j],a[i][j-]));
    //右上
    for(int i=n;i;i--)
        for(int j=;j<=m;j++)
            b[i][j]=max(s[i+k-][j],max(b[i+][j],b[i][j-]));
    //左下
    for(int i=;i<=n;i++)
        for(int j=m;j;j--)
            c[i][j]=max(s[i][j+k-],max(c[i-][j],c[i][j+]));
    //右下
    for(int i=n;i;i--)
        for(int j=m;j;j--)
            d[i][j]=max(s[i+k-][j+k-],max(d[i+][j],d[i][j+]));

    //兩豎線
    for(int i=k;i<=n-k*;i++)
        for(int j=k;j<=m;j++)
            ans=max(ans,a[i][m]+s[i+k][j]+b[i+k+][m]);
    //兩橫線
    for(int i=k;i<=m-k*;i++)
        for(int j=k;j<=m;j++)
            ans=max(ans,b[][i]+s[j][i+k]+c[n][i+k+]);
    //一豎線左邊一橫線
    for(int i=k;i<=n-k;i++)
        for(int j=k;j<=m-k;j++)
            ans=max(ans,a[i][j]+c[i][j+]+d[i+][]);
    //一豎線右邊一橫線
    for(int i=k;i<=n-k;i++)
        for(int j=k;j<=m-k;j++)
            ans=max(ans,a[i][m]+b[i+][j]+d[i+][j+]);
    //一橫線上邊一豎線
    for(int i=k;i<=m-k;i++)
        for(int j=k;j<=n-k;j++)
            ans=max(ans,a[i][j]+b[i+][j]+d[][j+]);
    //一橫線上邊一豎線
    for(int i=k;i<=m-k;i++)
        for(int j=k;j<=n-k;j++)
            ans=max(ans,b[i][]+c[i+][j]+d[i+][j+]);
    cout<<ans;
    return ; 
}