自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

搬运于2025-08-24 22:29:37，当前版本为作者最后更新于2021-04-18 16:31:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意：对于前 $i$ 个奶牛，求加入最少的奶牛的数目使不存在舒适的牛，即有三个牛在他身边。

我们来动态的考虑，每加进一个点会对前 $i-1$ 个点的影响。

1. 产生具有舒适度的奶牛。

2. 将以前加入的奶牛覆盖。

于是我们就可以发现对于前$i$个奶牛, $ans$ 可由前 $i-1$ 个奶牛状态得到，并且发现如果存在舒适的奶牛，取笑他舒适的奶牛是必须要加的。

加入的那个点很显然也是满足上述两种影响.

• 存图的时候下标可能会超出边界，就考虑极限，让每个坐标的值加 $1000$.

• 不要忘记加上的点自身也可能会是舒适的奶牛，所以不要忘记递归该点。

$summary$：

动态加点，递归处理

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 10010
using namespace std;
int re() {
	int p=0; char i=getchar();
	while(i<'0'||i>'9')	i=getchar();
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return p;
}
int n,m,cnt;
int map[N][N];
const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
void dfs(int x,int y)
{
	int flag=0;
	int t_x,t_y;
	if(!map[x][y])	return ;		//牛都不是
	for(int i=1;i<=4;i++) {
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(map[xx][yy]) flag++;
		else t_x=xx,t_y=yy;
	}
	if(flag!=3)	return ;		//牛不舒适，不用加点
	else {
		map[t_x][t_y]=1;
		cnt++;						//第一种影响
		for(int i=0;i<=4;i++)		//0是该点
			dfs(t_x+dx[i],t_y+dy[i]);
	}
}
int main()
{
	n=re();
	while(n--)
	{
		int x,y;
		x=re()+1000; y=re()+1000;	//防止数组超界
		if(map[x][y])	cnt--;		//第二种影响
		map[x][y]=1;
		for(int i=0;i<=4;i++)		//0是该点
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			dfs(xx,yy);
		}
		printf("%d\n",cnt);
	}
	return 0;
}

如有不妥，请不要吝啬您的评论 $qwq$.

题外话：为什么不是 $Farmer John$