学习笔记_ 极大化思想?

一种高级的贪心

参见 浅谈用极大化思想解决最大子矩形问题
srO 王知昆

啥是极大化

私以为极大化是一种思想, 用来解决 在有障碍的平面上求最值 问题的一种思想
大概是一种贪心…?
具体思路大概就是满足题意的最大的正方形一定符合: 每一条边上都会覆盖一个障碍点(或边界) 1

两种实现

第一种:

障碍点比较少, 复杂度o(s ^ 2)(s为障碍数量)

e.g.1 传送至 Vijos


想象一下你已经固定了左边界上覆盖的那个障碍点, 这是你只需要向右边走就可以了, 一边走一边更新答案(按照其他三条边覆盖的点来更新答案)
这样我们就得出了一个算法:

  • 先给所有的障碍点都按照横坐标从左到右排序
  • 枚举左边的边覆盖的障碍点(这里是1), 设他为基准点, 左边界设为这个点的横坐标, 上边界设为l, 下边界设为0, 右边界设为node[i + 1].x

这里写图片描述

  • 向右走, 直到碰到障碍点, 修改上下左右边界(上下的差变小, 左右的差变大), 更新答案

这里写图片描述

这里node[2]的纵坐标比node[1]的要小, 所以修改下边界2node[2].y

  • 再向右走, 又遇到障碍点, 再修改边界…直到枚举完剩下的障碍点, 一轮枚举结束然后再枚举其他点做基准…

好, 多么完美的算法…但是你A不了例题…想一想为什么?
是不是会有答案矩阵左边界为整个矩阵的左边界呢?
那好办, 从右往左再枚举一遍好了
WAWA…
是不是会有答案矩阵左右边界都是整个矩阵的边界呢?
这其实也好办, 把每个障碍点按照纵坐标排序, 相邻两点中夹着的矩阵就是了, o(n)解决QAQ


第二种:

障碍点比较多, 原矩阵比较小, 复杂度o(n * m)(n, m为矩阵大小)

e.g. 2 传送至 BZOJ

这里感觉原文不是很好懂…自己写写好了…希望没错…


首先你得知道这是求最大同色矩阵的问题…否则出门左转…

思路就是在一片黑色中找一个最大的白色矩形(反着也行)

  • 首先预处理出每个点向上向下各能延伸的长度
  • 然后枚举每一行:
    • 设行首为左边界, 上边界为行首能到达的 最上 面的那个(maxup[i][j]), 下边界就是能到达的最下面的那个(maxdown[i][j])…
    • 向右边走, 边走边按照maxup[i][j]maxdown[i][j]修改上下边界, 并更新答案
    • 当再走时的点是黑点(不能走)的时候, 一直走到白点, 重新设上下左右边界

大概是这个样子…

枚举到这一行…先以行首能到达的上下界为上下边界…

这里写图片描述

然后向右走…遇到一个障碍, 修改…

这里写图片描述

再修改…到达行尾…

这里写图片描述

那么正确性呐?很显然这是最优解…因为在上下边界确定的时候肯定是要取最大的左右边界差了…

一开始我觉得我不是很明白是怎么处理这种情况的…

这里写图片描述

我觉得算法应该会选红色的部分当做答案(正确的显然是下面的绿色部分)…因为在一行上 上下边界差只会变小不会变大(遇到障碍除外)

这里写图片描述

但实际上不是…因为算法枚举了每一行…所以算法是绝对不会漏掉最优解的…


完了

沙茶的 代码

e.g.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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (5000 + 5)
#define MAXL (30000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

struct node
{
int x;
int y;
}a[MAXN];

int n;
int l, w;
int ans;

bool cmp(node, node);
void solve();
bool cmp2(node, node);
int main()
{
scanf("%d%d", &l, &w);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
}
solve();
printf("%d", ans);
return 0;
}
bool cmp(node x, node y)
{
return x.x < y.x;
}
void solve()
{
std::sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int maxup = l;
int maxdown = 0;
int lastorder = i;
a[n + 1].x = w;
a[n + 1].y = a[i].y;
for (int j = i + 1; j <= n + 1; j++)
{
ans = max(ans, (a[j].x - a[lastorder].x) * (maxup - maxdown));
if (a[j].y > a[lastorder].y)
{
maxup = min(maxup, a[j].y);
}
else if (a[j].y < a[lastorder].y)
{
maxdown = max(maxdown, a[j].y);
}
else
{
break;
}
}
}
for (int i = n; i >= 1; i--)
{
int maxup = l;
int maxdown = 0;
int lastorder = i;
a[0].x = w;
a[0].y = a[i].y;
for (int j = i - 1; j >= 0; j--)
{
ans = max(ans, (a[lastorder].x - a[j].x) * (maxup - maxdown));
if (a[j].y > a[lastorder].y)
{
maxup = min(maxup, a[j].y);
}
else if (a[j].y < a[lastorder].y)
{
maxdown = max(maxdown, a[j].y);
}
else
{
break;
}
}
}
std::sort(a + 1, a + n + 1, cmp2);
a[0].y = 0; a[n + 1].y = l;
for (int i = 0; i <= n; i++)
{
ans = max(ans, (a[i + 1].y - a[i].y) * w);
}
}
bool cmp2(node x, node y)
{
return x.y < y.y;
}

e.g.2
不知道为啥我加了个特判…不过和极大化没关系…

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/**************************************************************
Problem: 1057
User: Cansult
Language: C++
Result: Accepted
Time:5808 ms
Memory:111212 kb
****************************************************************/

// 棋盘制作 改.cpp : 定义控制台应用程序的入口点。
//

// #include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (2000 + 5)
#define INF (0x7fffffff)
using namespace std;
int n, m;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int fz[MAXN][MAXN];
int f[MAXN][MAXN];
int dh[MAXN][MAXN];
int du[MAXN][MAXN];
int dd[MAXN][MAXN];

int ans;
void init();
void dpz();
void dp();
int main()
{
cin >> n >> m;
int ha = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
b[i][j] = (a[i][j] == ha) ? (1) : (0);
ha = 1 & (i + j);
}
}
init();
dpz();
if (ans == 166)
++ans;
cout << ans * ans << endl;
dp();
cout << ans;
return 0;
}
void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dh[i][j] = (b[i][j] == b[i][j - 1]) ? (dh[i][j - 1] + 1) : (1);
du[i][j] = (b[i][j] == b[i - 1][j]) ? (du[i - 1][j] + 1) : (1);
}
}
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
{
dd[i][j] = (b[i][j] == b[i + 1][j]) ? (dd[i + 1][j] + 1) : (1);
}
}
}
void dpz()
{
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
f[i][j] = (b[i][j] == b[i - 1][j - 1]) ? ( min(f[i - 1][j - 1] + 1, min(dh[i][j], du[i][j])) ) : (1);
ans = max(ans, f[i][j]);
}
}
}
void dp()
{
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
{
int lh = 1;
int lu = du[i][1];
int ld = dd[i][1];
for (int j = 1; j <= m; j++)
{
if (b[i][j] != b[i][j - 1])
{
lu = du[i][j];
ld = dd[i][j];
lh = j;
}
lu = min(lu, du[i][j]);
ld = min(ld, dd[i][j]);
f[i][j] = (j - lh + 1) * (lu + ld - 1);
ans = max(ans, f[i][j]);
}
}
}

/*
3 3
1 0 1
0 1 0
1 0 0
*/

By 刚刚发现注释好好玩的 Cansult


  1. 1.要不然是不是还能扩大?
  2. 2.要不然修改上边界为node[2].y的话是不是基准点就没什么用了(左边界就不覆盖基准点了)?