题目传送门
正方形DP
#include <bits/stdc++.h> using namespace std; // 全局变量定义 int n, t; // n: 农场大小（n×n），t: 果树数量 int a[1010][1010]; // 原始农场地图：a[i][j] = 1 表示有树，0 表示空地 int f[1010][1010]; // DP 数组：f[i][j] 表示以 (i, j) 为右下角的最大空旷正方形的边长 int ans = 0; // 记录全局最大正方形边长 int main() { // 输入农场大小 n 和果树数量 t cin >> n >> t; int x, y; // 读入 t 棵果树的位置，并在地图中标记为 1（表示不可用） while (t--) { cin >> x >> y; a[x][y] = 1; // 注意：题目坐标从 1 开始，直接使用即可 } // 动态规划填表：遍历整个 n×n 农场 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 如果当前位置是空地（没有树） if (a[i][j] == 0) { // 状态转移方程： // f[i][j] = min(左边, 上边, 左上角) + 1 // 原理：要形成更大的正方形，左、上、左上三个方向必须都能支撑 f[i][j] = min( min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1] ) + 1; } // 如果 a[i][j] == 1（有树），则 f[i][j] 保持为 0（无法作为正方形的一部分） // 更新全局最大边长 ans = max(ans, f[i][j]); } } // 输出最大可建牛棚的边长 cout << ans; return 0; }
悬线法DP
#include<bits/stdc++.h> using namespace std; const int N=1010; int a[N][N],l[N][N],r[N][N],u[N][N]; int n,t,ans=0; int main() { scanf("%d%d",&n,&t); int x,y; while(t--) { scanf("%d%d",&x,&y); a[x][y]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]==0){ l[i][j]=r[i][j]=j; u[i][j]=1; } } } // 向左扩展：计算每行每个位置能向左延伸到的最左列 for (int i = 1; i <= n; ++i) for (int j = 2; j <= n; ++j) if (!a[i][j] && !a[i][j - 1]) l[i][j] = l[i][j - 1]; // 向右扩展：计算每行每个位置能向右延伸到的最右列 for (int i = 1; i <= n; ++i) for (int j = n - 1; j >= 1; --j) if (!a[i][j] && !a[i][j + 1]) r[i][j] = r[i][j + 1]; // 向上扩展：计算每个位置向上连续空地的高度 for (int i = 2; i <= n; ++i) for (int j = 1; j <= n; ++j) if (!a[i][j] && !a[i - 1][j]) u[i][j] = u[i - 1][j] + 1; // 动态维护左右边界并更新答案 for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { // 如果不在第一行，且当前和上方都是空地，则继承上一行的左右边界（取更紧的） if (i != 1 && !a[i][j] && !a[i - 1][j]) { l[i][j] = max(l[i][j], l[i - 1][j]); r[i][j] = min(r[i][j], r[i - 1][j]); } // 当前位置能形成的最大正方形边长 = min(宽度, 高度) // 宽度 = r[i][j] - l[i][j] + 1，高度 = Up[i][j] ans = max(ans, min(r[i][j] - l[i][j] + 1, u[i][j])); } cout << ans << endl; return 0; }
