题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】
Jayun
·
·
题解
思路：
这道题很水，但很适合dp初学者做！（瞎扯一下）
先写动态转移方程，待会解释
f_{i,j}=min\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}\}+1
(a_{i,j}!=\#)
解释：
用**jio**指头想想就能知道，$f_{i,j}$是由左、上、左上方向来的
用$min$的原因是，如果用$max$,三个方向的正方形可能会碰到树,以及其它情况（蒟蒻表达不出来，看栗子~）.
拿样例解释：
```pascal
. . . . . . . .
. # . . . # . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . # . . . . .
. . . . . . . .
. . . . . . . .
```
用$max$:
```pascal
1 1 1 1 1 1 1 1
2 0 2 3 4 0 2 3
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 0 9 10 11 12 13
8 9 10 11 12 13 14 15
9 10 11 12 13 14 15 16
```
实际：
```pascal
1 1 1 1 1 1 1 1
1 0 1 2 2 0 1 2
1 1 1 2 3 1 1 2
```
（前几行，我累了。。。）
对比一下，用$max$根本不可能
## 代码
### 创建美好洛谷，切勿Ctrl+C
c++党这里↓
```cpp
#inculde<bits/stdc++.h>
using namespace std;
int n,t;
int f[1010][1010];
int ans;
int main() {
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=1; //边界条件哦
while(t--)
{
int x,y;
scanf("%d%d",&x,&y);
f[x][y]=0; //树的位置打零
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) //i和j千万不要从2开始哦
{
if(f[i][j]==0)continue;
f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1; //转移方程哦
ans=max(ans,f[i][j]); //更新目标
}
}
printf("%d",ans); //输出yeah
return 0; //。。。yeah
}
```
---
p党在这里哦~
```pascal
var
f:array[0..1010,0..1010]of longint;//注意是从0开始
x,y,i,j,n,t,ans:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
function mx(a,b:longint):longint;
begin
if a<b then exit(b)
else exit(a);
end;
begin
readln(n,t);
for i:=1 to n do
for j:=1 to n do
f[i,j]:=1; //边界条件
for i:=1 to t do
begin
readln(x,y);
f[x,y]:=0; //树的位置打零
end;
for i:=1 to n do
for j:=1 to n do
begin
if f[i,j]=0 then continue;
f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1; //转移方程
ans:=max(ans,f[i,j]); //更新目标
end;
writeln(ans); //yeah~
end.
```
希望你喜欢（暗示点赞