Loading... ## 题目 [洛谷 P2733 \[USACO3.3\]家的范围 Home on the Range](https://www.luogu.com.cn/problem/P2733) ### 描述 农民约翰在一片边长是N (2 <= N <= 250)英里的正方形牧场上放牧他的奶牛。 (因为一些原因，他的奶牛只在正方形的牧场上吃草。) 遗憾的是,他的奶牛已经毁坏一些土地。( 一些1平方英里的正方形) 农民约翰需要统计那些可以放牧奶牛的正方形牧场(至少是2x2的,在这些较大的正方形中没有小于1x1的部分被分割毁坏)。 你的工作要在被供应的数据组里面统计所有不同的正方形放牧区域(>2x2)的个数。 当然，放牧区域可能是重叠。 ### 输入 第 1 行：N,牧区的边长。 第 2 到n+1行：N个没有空格分开的字符。0 表示 "那一个区段被毁坏了";1 表示 " 准备好被吃"。 ### 输出 输出那些存在的正方形的大小和个数，一种一行。 ## 题解 这是一个矩阵DP问题。状态看似是二维的，可和区间DP有区别：在本题中可以用f[x*n+y]表示f[x][y]；区间DP的二维状态所表示的有左右边界的区间无法压缩成一维。 回到正题，我使用f[x][y]表示以点(x,y)为右下角的最大的正方形的边长。r表示边长为i的正方形有r[i]个，并且当r[i]=0，r[i+1]=1。  如上图，框中的数字表示以此点为右下角的最大正方形的边长。可得出，一个正方形的大小取决于它上，左上和左正方形边长，即它们的最短边长。不用多说，当a[i][j]=1，f[i][j]>1。 ## 代码 ``` #include <cstdio> #include <algorithm> int n, f[250][250], r[250]; bool a[250][250]; int find(int x, int y){ if(x == 0 || y == 0) return a[x][y]; if(f[x][y]) return f[x][y]; if(a[x][y]) f[x][y] = std::min(std::min(find(x-1, y-1), find(x, y-1)), find(x-1, y))+1; for(int i = 1; i <= f[x][y]; ++i){ ++r[i]; } return f[x][y]; } int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i){ char line[300]; scanf("%s", line); for(int j = 0; j < n; ++j){ a[i][j] = line[j]-'0'; } } for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(a[i][j]) find(i, j); } } for(int i = 2; i <= n; ++i){ if(r[i]) printf("%d %d\n", i, r[i]); else break; } return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
