悬线法dp总结

简介

所谓悬线，就是用一条线尽可能向两边拓展形成一个矩形，这样一条线就会构成矩形的宽。（原谅我也很难说明白悬线的具体定义）

用途

解决给定矩阵中满足条件的最大子矩阵

正确性

悬线法的正确性怎么证明？我们考虑最优解所代表的矩形（即满足条件的最大矩形），它的宽 $h$h 一定来自于某一条悬线。可以用反证法，假设它的宽不来自于任意一条悬线，即每条悬线都比宽 $h$h
大，这样我们显然可以得到一个更大的解，与条件矛盾。所以悬线法不一定能覆盖所有矩形，但一定可以覆盖到最优解的。

悬线法的具体实现

$f\left[i\right]\left[j\right]$f[i][j]表示以 $(i,j)$(i,j)往左所能拓展的最大距离
$g\left[i\right]\left[j\right]$g[i][j]表示以 $(i,j)$(i,j)往右所能拓展的最大距离
$w\left[i\right]\left[j\right]$w[i][j]表示以 $\left(i.j\right)$(i.j)往上所能拓展的最大距离
在这里我们以 $w\left[i\right]\left[j\right]$w[i][j]作为悬线，那么悬线所能向左和向右拓展的距离就按以下代码：

if(满足条件){
	w[i][j] = w[i-1][j] + 1;
	f[i][j] = min(f[i][j], f[i-1][j]);
	g[i][j] = min(g[i][j], g[i-1][j]);
}

然后我们就可以得到最大矩阵了

以一道题作为例题吧（ZJOI2007棋盘制作）

代码如下

#include <bits/stdc++.h>
#define N 2005
using namespace std;
int mp[N][N], f[N][N], g[N][N], w[N][N], ans1, ans2;
int main(){
	int i, j, n, m, c;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			scanf("%d", &mp[i][j]);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			if(j > 1 && mp[i][j] != mp[i][j-1]) f[i][j] = f[i][j-1] + 1;
			else f[i][j] = 1;
		}
		for(j = m; j >= 1; j--){
			if(j < m && mp[i][j] != mp[i][j+1]) g[i][j] = g[i][j+1] + 1;
			else g[i][j] = 1;
		}
	} 
	for(j = 1; j <= m; j++){
		for(i = 1; i <= n; i++){
			if(i > 1 && mp[i][j] != mp[i-1][j]){
				w[i][j] = w[i-1][j] + 1;
				f[i][j] = min(f[i][j], f[i-1][j]);
				g[i][j] = min(g[i][j], g[i-1][j]);
			}
			else w[i][j] = 1;
		}
	}
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++){
			c = min(w[i][j], f[i][j] + g[i][j] - 1);
			ans1 = max(ans1, c * c);
			ans2 = max(ans2, w[i][j] * (f[i][j] + g[i][j] - 1));
		}
	printf("%d\n%d", ans1, ans2);
	return 0;
}

练习

洛谷

p4147玉蟾宫
p2701巨大的牛棚