题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】

题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】

题面

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。

他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。

我们假定,他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚。

牛棚的边必须和水平轴或者垂直轴平行。

题意

给你一个图,要求找出图中符合规则的最大正方形。

题意同: P1387 最大正方形

题解

这是一道非常经典的矩阵(二维)动态规划,还有一道相似的题目: P1508 Likecloud-吃、吃、吃
(学会一道题,然后三倍经验😀)

遇到矩阵(二维)动态规划的题目,常规的思路就是手动构造->找状态转移方程。

非常规的思路就是:”这题我做个类似的,这个状态转移方程我知道!”


  • 首先画一个图,这是一个原始的图。
0 1 1 0 1
1 1 1 1 0
0 1 1 1 0
1 1 1 1 0
0 1 1 0 1
  • 然后构造出每一个点的最大正方形边长。
0 1 1 0 1
1 1 2 1 0
0 1 2 2 0
1 1 2 3 0
0 1 2 0 1
  • 由下图和上图可推出状态转移方程 : $ dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1 $

  • 最后只需要找出整个图中最大的点就行了。

代码

动态规划的题目的代码都非常的简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

int n,m,mapp[1010][1010];
int dp[1010][1010];

int main(int argc, char const *argv[])
{
cin >> n >> m;
memset(mapp,1,sizeof(mapp));
for(int i = 1;i <= m;++i)
{
int x,y;
cin >> x >> y;
mapp[x][y] = 0;
}

int maxx = -1;

for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
if(mapp[i][j])
{
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
maxx = max(maxx,dp[i][j]);
}
}

cout << maxx;

return 0;
}
本站文章除注明转载外均为原创,未经允许不要转载哇. ヾ(゚ー゚ヾ) http://chicago01.top/2018/11/07/题解 P2701 【[USACO5.3]巨大的牛棚Big Barn】/index.html
Compartir