洛谷——p2701[usaco5.3]巨大的牛棚bigbarn

author author     2022-09-21     710

关键词:

P2701 [USACO5.3]巨大的牛棚Big Barn

题目背景

(USACO 5.3.4)

题目描述

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。

EXAMPLE

考虑下面的方格,它表示农夫约翰的农场,‘.‘表示没有树的方格,‘#‘表示有树的方格

1 2 3 4 5 6 7 8

1 . . . . . . . .

2 . # . . . # . .

3 . . . . . . . .

4 . . . . . . . .

5 . . . . . . . .

6 . . # . . . . .

7 . . . . . . . .

8 . . . . . . . .

最大的牛棚是 5 x 5 的,可以建造在方格右下角的两个位置其中一个。

输入输出格式

输入格式:

 

Line 1: 两个整数: N (1 <= N <= 1000),农场的大小,和 T (1 <= T <= 10,000)有树的方格的数量

Lines 2..T+1: 两个整数(1 <= 整数 <= N), 有树格子的横纵坐标

 

输出格式:

 

只由一行组成,约翰的牛棚的最大边长。

 

输入输出样例

输入样例#1:
8 3
2 2
2 6
6 3
输出样例#1:
5

说明

题目翻译来自NOCOW。

USACO Training Section 5.3

 

 

简单的枚举

技术分享
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,y,a[1100][1100],sum;
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<0||ch>9) ch=getchar();
    while(ch>=0&&ch<=9) x=x*10+ch-0,ch=getchar();
    return x*f;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++) 
     x=read(),y=read(),a[x][y]=1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for(int k=n;k>=0;k--)
    {
        for(int i=1;i<=n-k+1;i++)
         for(int j=1;j<=n-k+1;j++)
         {
             int x=i+k-1,y=j+k-1;
             if(a[x][y]-a[i-1][y]-a[x][j-1]+a[i-1][j-1]==0)
             {printf("%d",k); return 0;}
          } 
    }
}
T成狗了

dp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,y,a[1100][1100],f[1100][1100],ans;
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<0||ch>9) ch=getchar();
    while(ch>=0&&ch<=9) x=x*10+ch-0,ch=getchar();
    return x*f;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++) 
     x=read(),y=read(),a[x][y]=1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      if(a[i][j]) continue;
      else f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      ans=max(ans,f[i][j]);
    printf("%d",ans);
    return 0;
}

 

洛谷——p2701[usaco5.3]巨大的牛棚bigbarn

https://www.luogu.org/problem/show?pid=2701题目背景(USACO5.3.4)题目描述农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划... 查看详情

洛谷p2701[usaco5.3]巨大的牛棚bigbarnlabel:二维数组前缀和你够了这次我用dp

题目背景(USACO5.3.4)题目描述农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成NxN的方格。输入数据中包括... 查看详情

题解p2701[usaco5.3]巨大的牛棚bigbarn(代码片段)

题面农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成NxN的方格。输入数据中包括有树的方格的列表。你的任... 查看详情

洛谷[p2701]巨大的牛棚

首先,本题是一道最大子矩阵问题,且m,n较小,可以使用DP做,与洛谷[P1387]最大正方形做法相同。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cstdlib>#include<cmath>usingnamesp 查看详情

[usaco5.3]巨大的牛棚bigbarn

题目背景(USACO5.3.4)题目描述农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成NxN的方格。输入数据中包括... 查看详情

[usaco5.3]巨大的牛棚bigbarn

[TimeGate]https://www.luogu.org/problem/P2701【解题思路】f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;f(i,j)表示以(i,j)为右下角的最大正方形的边长。【code】1#include<cstdio>2#include<iostream>3#include<al 查看详情

[iddfs+背包]洛谷p2744[usaco5.3]量取牛奶milkmeasuring

折腾了好几天的题目,简单讲讲心得。首先看了题解才写出来的,因为有一个核心的一点没想到,用桶的数量当迭代加深搜索的层数,算是长见识了~每次dp数组的初始化自己手动赋值0,不然会TLE一个点。思路:以桶的数量作为... 查看详情

洛谷p1209修理牛棚==codevs2079修理牛棚

时间限制:1s  空间限制:128000KB  题目等级:黄金Gold题目描述 Description在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被... 查看详情

洛谷p1209[usaco1.3]修理牛棚barnrepair

P1209[USACO1.3]修理牛棚BarnRepair题目描述在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛... 查看详情

洛谷p1209[usaco1.3]修理牛棚barnrepair

题目描述在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛,有些没有。所有的牛棚有相... 查看详情

洛谷p1209[usaco1.3]修理牛棚barnrepair

 题目描述在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛,有些没有。所有的牛棚... 查看详情

洛谷——p1209[usaco1.3]修理牛棚barnrepair

https://www.luogu.org/problem/show?pid=1209题目描述在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里... 查看详情

洛谷p2242公路维修问题(road)

题目描述在一个夜黑风高,下着暴风雨的夜晚,farmerJohn的牛棚的屋顶、门被吹飞了。好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛,有些没有。所有的牛棚有相... 查看详情

[usaco5.3]量取牛奶milkmeasuring

题目描述农夫约翰要量取Q(1<=Q<=20,000)夸脱(夸脱,quarts,容积单位——译者注)他的最好的牛奶,并把它装入一个大瓶子中卖出。消费者要多少,他就给多少,从不有任何误差。农夫约翰总是很节约。他现在在奶牛... 查看详情

luogup2744[usaco5.3]量取牛奶milkmeasuring

题目描述农夫约翰要量取Q(1<=Q<=20,000)夸脱(夸脱,quarts,容积单位——译者注)他的最好的牛奶,并把它装入一个大瓶子中卖出。消费者要多少,他就给多少,从不有任何误差。农夫约翰总是很节约。他现在在奶牛... 查看详情

p2746[usaco5.3]校园网networkofschools强连通(代码片段)

  题目描述一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使B在A学校的分发列表中,A也不一定在B学校的列表中。你要写一个程序计算,根... 查看详情

洛谷p2341[haoi2006]受欢迎的牛

题目描述每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B,B喜欢C,那么A也喜欢C。牛栏里共有N... 查看详情

洛谷p1113杂务

题目描述John的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才... 查看详情