| 题目名称 | 909. 巨大的牛棚 |
|---|---|
| 输入输出 | bigbrn.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 15 |
| 题目来源 |
 sywgz
于2012-07-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：44， 提交：89， 通过率：49.44% | ||||
 521 |
100 | 0.020 s | 0.86 MiB | C++ |
 水中音 |
100 | 0.038 s | 1.28 MiB | C++ |
 Lee Sin |
100 | 0.040 s | 1.28 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.042 s | 1.28 MiB | C++ |
 kevin741 |
100 | 0.047 s | 3.36 MiB | C++ |
 ch3coooh |
100 | 0.048 s | 3.89 MiB | C++ |
 mikumikumi |
100 | 0.053 s | 4.83 MiB | C++ |
 raywzy |
100 | 0.065 s | 7.96 MiB | C++ |
 葳棠殇 |
100 | 0.073 s | 1.17 MiB | C++ |
 甘罗 |
100 | 0.075 s | 8.09 MiB | C++ |
| 本题关联比赛 | |||
| 论文练习 | |||
| 关于 巨大的牛棚 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int p[1010][1010][2],n,m,bk[1010][1010],f[1010][1010][3],ma=1,a1,a2; int main(){ freopen("bigbrn.in","r",stdin); freopen("bigbrn.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a1,&a2); bk[a1][a2]=1; } for(int i=1;i<=n;i++){ if(bk[i][1])p[i][1][0]=1; else p[i][1][0]=2; for(int j=2;j<=n;j++){ if(bk[i][j]==0)p[i][j][0]=p[i][j-1][0]; else p[i][j][0]=j+1; } } for(int i=1;i<=n;i++){ if(bk[i][n]==0)p[i][n][1]=n; else p[i][n][1]=n-1; for(int j=n-1;j>=1;j--){ if(bk[i][j]==0)p[i][j][1]=p[i][j+1][1]; else p[i][j][1]=j-1; } } for(int i=1;i<=n;i++){ if(bk[1][i]==0)f[1][i][0]=1,f[1][i][1]=p[1][i][0],f[1][i][2]=p[1][i][1]; else f[1][i][0]=2,f[1][i][1]=1,f[1][i][2]=n; } for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++){ if(bk[i][j]==0){ f[i][j][0]=f[i-1][j][0]; f[i][j][1]=max(p[i][j][0],f[i-1][j][1]); f[i][j][2]=min(p[i][j][1],f[i-1][j][2]); } else{ f[i][j][0]=i+1; f[i][j][1]=1; f[i][j][2]=n; } if(bk[i][j]==0)ma=max(ma,min(i-f[i][j][0]+1,f[i][j][2]-f[i][j][1]+1)); } } printf("%d",ma); return 0; }
 贺越云
2018-11-10 10:07
7楼
| ||||
|
百题斩~~~~~~~~~~~
 ShallowDream雨梨
2018-11-08 18:42
6楼
| ||||
|
实在不太懂悬线法。。。
索性用动规写了。。。 | ||||
|
悬线~
| ||||
|
动归+滚动
| ||||
|
和“家的范围”n^2算法一样一样滴
| ||||
|
第一次广搜On3，以为不会超时，还是DP吧。
| ||||
Zwoi_只会打表抄代码的蒟蒻
liu_runda
cstdio
USACO/bigbrn(译 by Felicia Crazy)
描述
农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。EXAMPLE
考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。
PROGRAM NAME: bigbrn
INPUT FORMAT(file bigbrn.in)
| Line 1: | 两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10，000）有树的方格的数量 |
| Lines 2..T+1: | 两个整数（1 <= 整数 <= N), 有树格子的横纵坐标 |
OUTPUT FORMAT(file bigbrn.out)
输出文件只由一行组成，约翰的牛棚的最大边长。
SAMPLE INPUT (file bigbrn.in)
8 3
2 2
2 6
6 3
SAMPLE OUTPUT (file bigbrn.out)
5