题解 P7411 【[USACO21FEB] Comfortable Cows S】

_zy_ · 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