洛谷 P3625 [APIO2009]采油区域【枚举】

参考：https://blog.csdn.net/FAreStorm/article/details/49200383

没有技术含量但是难想难写，枚举情况图详见参考blog懒得画了

bzoj蜜汁TTTTTTTTTTTTTTTLE

upd：bzoj数据有问题，快读GG

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=1505;

int n,m,k,a[N][N],b[N][N],c[N][N],d[N][N],s[N][N],p[N][N],h[N][N],l[N][N],mxh[N],mxl[N],ans;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read(),m=read(),k=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+read();

	for(int i=k;i<=n;i++)

		for(int j=k;j<=m;j++)

			p[i][j]=s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k],a[i][j]=max(p[i][j],max(a[i-1][j],a[i][j-1]));

	for(int i=k;i<=n;i++)

		for(int j=m-k+1;j>=1;j--)

			b[i][j]=max(p[i][j+k-1],max(b[i-1][j],b[i][j+1]));

	for(int i=n-k+1;i>=1;i--)

		for(int j=k;j<=m;j++)

			c[i][j]=max(p[i+k-1][j],max(c[i+1][j],c[i][j-1]));

	for(int i=n-k+1;i>=1;i--)

		for(int j=m-k+1;j>=1;j--)

			d[i][j]=max(p[i+k-1][j+k-1],max(d[i+1][j],d[i][j+1]));

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			mxh[i]=max(mxh[i],p[i][j]),mxl[j]=max(mxl[j],p[i][j]);

	for(int i=1;i<=n;i++)

	{

		h[i][i+k-1]=mxh[i+k-1];

		for(int j=i+k;j<=n;j++)

			h[i][j]=max(h[i][j-1],mxh[j]);

	}

	for(int i=1;i<=m;i++)

	{

		l[i][i+k-1]=mxl[i+k-1];

		for(int j=i+k;j<=m;j++)

			l[i][j]=max(l[i][j-1],mxl[j]);

	}

	for(int i=k;i<=n-k+1;i++)

		for(int j=k;j<=m-k+1;j++)

			ans=max(ans,max(max(a[i][j]+c[i+1][j]+l[j+1][m],l[1][j]+b[i][j+1]+d[i+1][j+1]),max(a[i][j]+b[i][j+1]+h[i+1][n],h[1][i]+c[i+1][j]+d[i+1][j+1])));

	for(int i=k;i<=n-k+1;i++)

		for(int j=i+k-1;j<=n-k+1;j++)

			ans=max(ans,h[1][i-1]+h[i][j]+h[j+1][n]);

	for(int i=k;i<=m-k+1;i++)

		for(int j=i+k-1;j<=m-k+1;j++)

			ans=max(ans,l[1][i-1]+l[i][j]+l[j+1][n]);

	printf("%d\n",ans);

	return 0;

}

巴特西

洛谷 P3625 [APIO2009]采油区域【枚举】

最新文章

热门文章