悬线法
什么是悬线法
oiwiki
1
2
3
4
5
6
| 悬线法的适用范围是单调栈的子集。具体来说，悬线法可以应用于满足以下条件的题目：
- 需要在扫描序列时维护单调的信息；
- 可以使用单调栈解决；
- 不需要在单调栈上二分。
看起来悬线法可以被替代，用处不大，但是悬线法概念比单调栈简单，更适合初学 OI 的选手理解并解决最大子矩阵等问题。
|
1
2
3
4
5
6
7
8
9
10
11
12
| 何为悬线法
悬线的定义是这样的：
**从每一个点向上走，知道遇到障碍点或顶边界。**
那么我们可以轻松地得到悬线的一些性质：
1. 每一个点对应一根悬线
2. 每一根悬线都对应了一个高度等于悬线高度，宽度大于0的矩形
所以悬线法的步骤就是：**找出每一个点对应的悬线的高度，然后向左右分别找出该悬线能拓展出的矩形的宽度。**
|
ps：悬线法本质上也是一种动态规划，因为悬线法的难点就在于对l数组和r数组的动态规划处理。
例题
HISTOGRA - Largest Rectangle in a Histogram
https://www.luogu.com.cn/problem/SP1805
解法一：悬线法
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin>>n,n)
{
vector<int>a(n+1),l(n+1),r(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)l[i]=r[i]=i;
for(int i=1;i<=n;i++)while(l[i]>1&&a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
for(int i=n;i>=1;i--)while(r[i]<n&&a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
int maxn=-inf;
for(int i=1;i<=n;i++)
{
int shu=(long long)(r[i]-l[i]+1)*a[i];
maxn=max(maxn,shu);
}
cout<<maxn<<'\n';
}
return 0;
}
|
解法二： 单调栈
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin>>n,n)
{
vector<int>l(n+1,0),r(n+1,n+1);
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>stk;
for(int i=1;i<=n;i++)
{
while(stk.size()&&a[i]<a[stk.top()])
{
r[stk.top()]=i;
stk.pop();
}
stk.push(i);
}
stack<int>stk1;
for(int i=n;i>=1;i--)
{
while(stk1.size()&&a[i]<a[stk1.top()])
{
l[stk1.top()]=i;
stk1.pop();
}
stk1.push(i);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ll shu=1ll*(r[i]-l[i]-1)*a[i];
ans=max(ans,shu);
}
cout<<ans<<'\n';
}
return 0;
}
|
感觉不错 Feel Good
https://www.luogu.com.cn/problem/UVA1619
这一题不能用STL，不然会超时！！！
注意有多组数据
注意出了最后一组数据，其他数据中间都有一个空行。
数据中有一个数据是全0，注意答案初始要为：
这一题的本质就是枚举最小值，将每一个a[i]当作最小值来处理，从i开始把区间向两边扩，使得a[i]是这个区间中的最小值。这样就可以用到悬线法来进行操作了。
解法一：悬线法
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
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 100010;
int a[N],l[N],r[N];
ll pre[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int vis=1;
int n;
while(cin>>n)
{
memset(a, -1, sizeof(a));
if(!vis)cout<<'\n';
else vis=0;
ll ans=0;
int ansl=1,ansr=1;
for(int i=1;i<=n;i++){
cin>>a[i];
l[i]=r[i]=i;
pre[i]=pre[i-1]+a[i];
}
for(int i=1;i<=n;i++)while(a[l[i]-1]>=a[i])l[i]=l[l[i]-1];
for(int i=n;i>=1;i--)while(a[r[i]+1]>=a[i])r[i]=r[r[i]+1];
for(int i=1;i<=n;i++)
{
ll shu=(pre[r[i]]-pre[l[i]-1])*a[i];
if(shu>ans||(shu==ans&&r[i]-l[i]+1<ansr-ansl+1))
{
ans=shu;
ansr=r[i],ansl=l[i];
}
}
cout<<ans<<'\n'<<ansl<<' '<<ansr<<'\n';
}
return 0;
}
|
解法二：单调栈
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=1e5+10;
int a[N],l[N],r[N];
ll pre[N];
int vis;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin>>n)
{
if(vis)cout<<'\n';
else vis++;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
stack<int>stk,stk1;
for(int i=1;i<=n;i++)
{
l[i]=0,r[i]=n+1;
}
for(int i=1;i<=n;i++)
{
while(stk.size()&&a[i]<a[stk.top()])
{
r[stk.top()]=i;
stk.pop();
}
stk.push(i);
}
for(int i=n;i>=1;i--)
{
while(stk1.size()&&a[i]<a[stk1.top()])
{
l[stk1.top()]=i;
stk1.pop();
}
stk1.push(i);
}
ll maxn=0;
int ansl=1,ansr=1;
for(int i=1;i<=n;i++)
{
ll shu=1ll*(pre[r[i]-1]-pre[l[i]])*a[i];
if(shu>maxn||(shu==maxn&&((r[i]-l[i]-1<ansr-ansl+1)||(r[i]-l[i]-1==ansr-ansl+1&&l[i]+1<ansl))))
{
maxn=shu;
ansl=l[i]+1,ansr=r[i]-1;
}
}
cout<<maxn<<'\n';
cout<<ansl<<" "<<ansr<<'\n';
}
return 0;
}
|
P4147 玉蟾宫
第一种是悬线法的做法，第二种是单调栈的做法。
这一题的悬线法跟https://www.luogu.com.cn/problem/SP1805的找最大矩形的思路几乎一模一样，只不过这个是对每层分别进行相似的步骤罢了。
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
if(ch=='F')dp[i][j]=dp[i-1][j]+1;
}
}
vector<int>l(m+1),r(m+1);
ll maxn=0;
auto ask=[&](int x){
for(int i=1;i<=m;i++)l[i]=r[i]=i;
auto &a=dp[x];
for(int j=1;j<=m;j++)while(l[j]>1&&a[j]<=a[l[j]-1])l[j]=l[l[j]-1];
for(int j=m;j>=1;j--)while(r[j]<m&&a[j]<=a[r[j]+1])r[j]=r[r[j]+1];
for(int i=1;i<=m;i++)
{
int shu=(r[i]-l[i]+1)*a[i];
maxn=max(maxn,1ll*shu);
}
};
for(int i=1;i<=n;i++)ask(i);
cout<<maxn*3<<'\n';
return 0;
}
|
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
ll maxn;
struct node
{
int len,h;
}a[1010];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
if(ch=='F')dp[i][j]=dp[i-1][j]+1;
}
}
auto ask=[&](int x){
memset(a,0,sizeof(a));
stack<node>stk;
for(int j=1;j<=m;j++)
{
int w=0;
while(stk.size()&&stk.top().h>=dp[x][j])
{
w+=stk.top().len;
maxn=max(maxn,1ll*w*stk.top().h);
stk.pop();
}
a[j].h=dp[x][j];a[j].len=w+1;
stk.push(a[j]);
}
int w=0;
while(stk.size())
{
w+=stk.top().len;
maxn=max(maxn,1ll*w*stk.top().h);
stk.pop();
}
};
for(int i=1;i<=n;i++)ask(i);
cout<<maxn*3<<'\n';
return 0;
}
|
P1169 [ZJOI2007] 棋盘制作
https://www.luogu.com.cn/problem/P1169
这一题还是很正常的悬线法，只不过l和r数组向两边扩的时候加了个限制条件（只有a[x][l[i]-1]!=a[x][l[i]]才能往左扩，向右扩同理。
这一题求最大矩形的面积就正常做就行了，求最大正方形的面积就是在每个矩形里面找到个最大正方形就行了。
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector dp(n+1,vector<int>(m+1,1)),a(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i-1][j]!=a[i][j])dp[i][j]+=dp[i-1][j];
}
}
ll maxn=0;
ll ret=0;
ll ansl,ansr,ceng,lie;
vector<int>l(m+1),r(m+1);
auto ask=[&](int x){
for(int i=1;i<=m;i++)l[i]=r[i]=i;
auto &h=dp[x];
for(int i=1;i<=m;i++)while(l[i]>1&&a[x][l[i]-1]!=a[x][l[i]]&&h[i]<=h[l[i]-1])l[i]=l[l[i]-1];
for(int i=m;i>=1;i--)while(r[i]<m&&a[x][r[i]+1]!=a[x][r[i]]&&h[i]<=h[r[i]+1])r[i]=r[r[i]+1];
for(int i=1;i<=m;i++)
{
ll shu=(r[i]-l[i]+1)*h[i];
maxn=max(maxn,shu);
ret=max(ret,(ll)pow(min(r[i]-l[i]+1,h[i]),2));
}
};
for(int i=1;i<=n;i++)
{
ask(i);
}
cout<<ret<<'\n'<<maxn<<'\n';
return 0;
}
|
P2701 [USACO5.3] 巨大的牛棚Big Barn
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,t;
cin>>n>>t;
vector<vector<int>>a(n+1,vector<int>(n+1)),dp(n+1,vector<int>(n+1));
for(int i=1;i<=t;i++)
{
int x,y;
cin>>x>>y;
a[x][y]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]!=1)dp[i][j]=dp[i-1][j]+1;
}
}
int ret=0;
vector<int>l(n+1),r(n+1);
for(int i=1;i<=n;i++)
{
auto &h=dp[i];
for(int j=1;j<=n;j++)l[j]=r[j]=j;
for(int j=1;j<=n;j++)while(l[j]>1&&h[j]<=h[l[j]-1])l[j]=l[l[j]-1];
for(int j=n;j>=1;j--)while(r[j]<n&&h[j]<=h[r[j]+1])r[j]=r[r[j]+1];
for(int i=1;i<=n;i++)
{
ret=max(ret,min(h[i],r[i]-l[i]+1));
}
}
cout<<ret<<'\n';
return 0;
}
|
P1387 最大正方形
第一种做法是悬线法，第二种做法是普通的动态规划，虽然悬线法也是动态规划。
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<int>>v(n+1,vector<int>(m+1)),dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cin>>v[i][j];
}
vector<int>l(m+1),r(m+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[i][j]==1)dp[i][j]=dp[i-1][j]+1;
}
}
int ret=0;
for(int i=1;i<=n;i++)
{
auto &a=dp[i];
for(int j=1;j<=m;j++)l[j]=r[j]=j;
for(int j=1;j<=m;j++)while(l[j]>1&&a[j]<=a[l[j]-1])l[j]=l[l[j]-1];
for(int j=m;j>=1;j--)while(r[j]<m&&a[j]<=a[r[j]+1])r[j]=r[r[j]+1];
for(int j=1;j<=m;j++)ret=max(ret,min(a[j],r[j]-l[j]+1));
}
cout<<ret<<'\n';
return 0;
}
|
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
| #include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<int>>v(n+1,vector<int>(m+1)),dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cin>>v[i][j];
}
int maxn=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[i][j]==1){
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
maxn=max(maxn,dp[i][j]);
}
}
}
cout<<maxn<<'\n';
}
|
wechat
