Algorithm2.10 坐标系dp
[TOC]
坐标系dp
区域最大：
- 最大正方形 <-> 最大正方形变式
- 最大矩形（包括正方形）
最大正方形
https://www.luogu.com.cn/problem/P1387
题目大意：给出一个二维坐标系中，找出里边全部是1的一个正方形的最大长度
初始化：维护一个dp[maxn][maxn],dp[i][j]表示在第i，j的这个点上的最大正方形
状态转移方程：
if (a[i][j]) dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1;
完整代码：
#include <iostream>
using namespace std;
const int maxn = 105;
int n, m, a[maxn][maxn], dp[maxn][maxn], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j]) dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1, ans = max(ans, dp[i][j]);
printf("%d\n", ans);
return 0;
}
最大矩形（包括正方形）
最大正方形变式
https://www.luogu.com.cn/problem/P1681
题目大意：变成01交换的正方形
初始化：维护dp_0[maxn][maxn], dp_1[maxn][maxn]分别表示ij这个坐标的点上的可以形成的最大正方形
状态转移方程：
if (a[i][j]) dp_1[i][j] = min(dp_1[i-1][j-1], min(dp_0[i-1][j], dp_0[i][j-1]))+1, ans = max(ans, dp_1[i][j]);
else dp_0[i][j] = min(dp_0[i-1][j-1], min(dp_1[i-1][j], dp_1[i][j-1]))+1, ans = max(ans, dp_0[i][j]);
完整代码：
#include <iostream>
using namespace std;
const int maxn = 1510;
int n, m, a[maxn][maxn], dp_0[maxn][maxn], dp_1[maxn][maxn], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j]) dp_1[i][j] = min(dp_1[i-1][j-1], min(dp_0[i-1][j], dp_0[i][j-1]))+1, ans = max(ans, dp_1[i][j]);
else dp_0[i][j] = min(dp_0[i-1][j-1], min(dp_1[i-1][j], dp_1[i][j-1]))+1, ans = max(ans, dp_0[i][j]);
printf("%d\n", ans);
return 0;
}