洛谷P1736 创意吃鱼法

P1736 创意吃鱼法

这道题目是一道dp问题

我们直接考虑dp数组的设置

用dp[i][j]表示在i j这个点的最优吃鱼方案

发现在dp[i][j]这个点的最优答案只与这个点上面能连起来的0的个数，左边或右边能连起来的0的个数和dp[i-1][j-1]或dp[i-1][j+1]有关

发现我们这样就只用维护三个数组

1.记录当前点左边或右边连续的0的个数

2.记录当前点上边连续的0的个数

3.记录当前点的最优方案

但是我们发现对角线有从左上到右下和从右上到左下之分

所以就会有左边和右边的0的个数之分

当然，dp方程也会不太一样

当我们取的是左上到右下时，s1记录左边连续0的个数

方程为：dp[i][j]=min(dp[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;

当我们取的是右上到左下时，s1记录右边连续0的个数

方程为：dp[i][j]=min(dp[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;

至于为啥取最小值，我们可以画一个图

根据图的意思来表示我们的方程为啥取min

也不是特别难理解

当然不是在枚举每一个的时候都需要去用这个dp方程

只有在a[i][j]为1时我们才会用到【a[i][j]存的是这个矩阵】

而当a[i][j]为0时我们得去维护或者更新s1数组和s2数组

在两次求dp的过程中【一次是左上到右下，另一次是右上到左下】

我们在中间需要重新memset这个s1数组和dp数组

从而不让两次dp产生干扰

最后取每个dp[i][j]的最优值即可，注意要分别取max,因为dp数组会在过程中被memset

下放代码

#include<bits/stdc++.h>
using namespace std;
int a[2501][2501],s1[2501][2501],s2[2501][2501],dp[2501][2501],ans;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			if(!a[i][j])
			{
				s1[i][j]=s1[i][j-1]+1;
				s2[i][j]=s2[i-1][j]+1;
			}
			else
				dp[i][j]=min(dp[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;
			ans=max(ans,dp[i][j]);
		}
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
		for(int j=m;j>=1;j--)
		{
			if(!a[i][j])
			{
				s1[i][j]=s1[i][j+1]+1;
				s2[i][j]=s2[i-1][j]+1;
			}
			else
				dp[i][j]=min(dp[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;
			ans=max(ans,dp[i][j]);
		}
	cout<<ans; 
	return 0; 
}