首页 > 其他分享 >悬线法

悬线法

时间:2024-10-04 09:22:06浏览次数:4  
标签:悬线法 int cin long while 例题

简单介绍

学习笔记

悬线法,相当于有一个限高绳,向左向右找到不低于这个高度的左右边界。

image

例题

SP1805 例题

分类讨论:

  • 当 \(l=1\),到达边界停止。

  • 当 \(a[i]>a[i-1]\),低于高度,停止拓展。

  • 当 \(a[i]<=a[i-1]\),可以扩展,直接继承 \(l[i]=l[l[i]-1]\)。

相同的求右端点,最后求最大矩阵面积就是左右边界距离乘高度。

点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;

int a[N];
int l[N],r[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(1){
    	cin>>n;
    	if(n==0){
    		break;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
			l[i]=i;
			r[i]=i;
		}
		for(int i=1;i<=n;i++){
			while(l[i]-1>=1&&a[i]<=a[l[i]-1]){
				l[i]=l[l[i]-1];
			}
		}
		for(int i=n;i>=1;i--){
			while(r[i]+1<=n&&a[i]<=a[r[i]+1]){
				r[i]=r[r[i]+1];
			}
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			ans=max(ans,(ll)(r[i]-l[i]+1)*a[i]);
		}
		cout<<ans<<"\n";
	}
    return 0;
}

标签:悬线法,int,cin,long,while,例题
From: https://www.cnblogs.com/sadlin/p/18446331

相关文章

  • 悬线法
    使用\(dp\)\(O(n*m)\)解决矩阵最大面积问题。两种解法,一种直接抄板子,但是需要将图抽象成为二维平面上,一些点固定可选,一些点固定不可选。换句话说,对于一个\(01\)矩阵,找出一个面积最大的矩形使得这个矩形内所有点都是\(1\)。另一种解法,悬线找出每个节点可以向上/下扩展的最......
  • 动态规划——悬线法
    动态规划——悬线法P4147玉蟾宫1//动态规划——悬线法2#include<iostream>3#include<cmath>4usingnamespacestd;5constintN=1010;6intn,m;7chara[N][N];8inth[N][N];//保存高度9intl[N][N],r[N][N];10intmain(){11cin>>n>>m;......
  • 5.8 单调栈 & 悬线法 & 相关的题(和 dp 也多少沾点)
    今日小题:一个CFdiv2的A的签到题,记录一下这个做法:求一个字符串的最长非回文字符串:无解:长度为1或整个串每个字符都一样;有解:判断这个串是不是回文,如果不是,输出长度,如果是输出长度-1。感觉非常妙。不写证明,感觉非常好想...#include<bits/stdc++.h>usingnamespacestd;i......
  • 悬线法学习笔记
    悬线法学习笔记单调栈可以解决的问题,一部分可以用悬线法解决,悬线法更容易理解,代码量差不多。SPOJ.com-ProblemHISTOGRA找元素的左右扩展区间。如果用选线法处理的话,......