DP(悬线法)+二维前缀和【p2706】巧克力

Background

王7的生日到了，他的弟弟准备送他巧克力。

Description

有一个被分成n*m格的巧克力盒，在(i,j)的位置上有a[i,j]块巧克力。就在送出它的前一天晚上，有老鼠夜袭巧克力盒，某些位置上被洗劫并且穿了洞。所以，你——王7的弟弟王9，必须从这个满目苍夷的盒子中切割出一个矩形巧克力盒，其中不能有被老鼠洗劫过的格子且使这个盒子里的巧克力尽量多。

Input

第一行有两个整数 n、m。第 i+1行的第 j 个数表示a[ i , j ]。如果这个数为 0 ，则表示这个位置的格子被洗劫过。

Output

输出最大巧克力数。

表示很水的一个题.要不是数据有问题我就切了

悬线法+二维前缀和。吼啊

不过貌似比只写二维前缀和的麻烦一点.

我们预处理出来悬线法用的数组.(记得变一下限制条件.

然后真正做悬线法的时候.

我们可以得到一个合法矩形.

其左上角坐标,右下角坐标均可求.

然后用二维前缀和算一下即可.

PS：这题数据有问题,读入矩阵的时候要用\(cin\)

代码

#include<cstdio>

#include<algorithm>

#include<iostream>

#define R register

#define N 308

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,ans;

int res[N][N],sum[N][N];

int ri[N][N],le[N][N],up[N][N];

inline int calc(int a,int b,int c,int d)

{

	return (sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1]);

}

int main()

{

	in(n),in(m);

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

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

		{

			cin>>res[i][j];

			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+res[i][j];

			ri[i][j]=le[i][j]=j;

			up[i][j]=1;

		}

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

		for(R int j=2;j<=m;j++)

			if(res[i][j] and res[i][j-1])

				le[i][j]=le[i][j-1];

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

		for(R int j=m-1;j>=1;j--)

			if(res[i][j] and res[i][j+1])

				ri[i][j]=ri[i][j+1];

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

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

		{

			if(res[i][j] and res[i-1][j])

			{

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

				ri[i][j]=min(ri[i][j],ri[i-1][j]);

				up[i][j]=up[i-1][j]+1;

			}

			int a=i-up[i][j]+1,b=le[i][j],c=i,d=ri[i][j];

			ans=max(ans,calc(a,b,c,d));

		}

	printf("%d",ans);

}

巴特西

DP(悬线法)+二维前缀和【p2706】巧克力

Background

Description

Input

Output

最新文章

热门文章