HLG 1408 漩涡

题意： 给你一个矩形范围，让你在这个矩形内找一个漩涡状的区域，使得和最大。

分析： 暴力枚举所有漩涡，有个注意的就是： 由于漩涡套漩涡，所以每个漩涡的值都等于该矩形区域的数字和减去刚好嵌在

　　　　该漩涡内的漩涡和左上角一个小缺口，画图很容易看出。

#include<stdio.h>
#include<string.h>
#define min(a,b)(a)<(b)?(a):(b)
#define max(a,b)(a)>(b)?(a):(b)
int c[500][500];
int c1[502][502];
int c2[502][502];
int n,m;
int h;
int lowbit(int x)
{return (x)&(-x);
}
void add(int x,int y,int w)
{while(x<=n){int ty=y;while(ty<=m){c[x][ty]+=w;ty+=lowbit(ty);}x+=lowbit(x);}
}
int sum(int x,int y)
{int s=0;while(x>0){int ty=y;while(ty>0){s+=c[x][ty];ty-=lowbit(ty);}x-=lowbit(x);}return s;
}
int s[502][502];
int g[502][502];
int main()
{int res,i,j,t,x,k;while(scanf("%d%d",&n,&m)!=EOF){memset(c,0,sizeof(c));t=min(n,m);for(i=1;i<=n;i++)for(j=1;j<=m;j++){scanf("%d",&x);g[i][j]=x;add(i,j,x);}for(i=1;i<=n;i++)for(j=1;j<=m;j++)c1[i][j]=g[i][j];for(i=1;i<=n;i++)for(j=1;j<=m;j++)s[i][j]=sum(i,j);res=-99999999;for(k=3;k<=t;k+=2){for(i=k;i<=n;i++)for(j=k;j<=m;j++){c2[i][j]=s[i][j];if(i>k)c2[i][j]-=s[i-k][j];if(j>k)c2[i][j]-=s[i][j-k];if(i>k&&j>k)c2[i][j]+=s[i-k][j-k];c2[i][j]=c2[i][j]-c1[i-1][j-1]-g[i-k+2][j-k+1];if(c2[i][j]>res)res=c2[i][j];}for(i=1;i<=n;i++)for(j=1;j<=m;j++)c1[i][j]=c2[i][j];}printf("%d\n",res);}return 0;
}