1531 山峰 【栈的应用】

简介: 题目连接:http://codevs.cn/problem/1531/题目描述 DescriptionRocky山脉有n个山峰,一字排开,从西向东依次编号为1, 2, 3, ……, n。每个山峰的高度都是不一样的。

题目连接:http://codevs.cn/problem/1531/

题目描述 Description

Rocky山脉有n个山峰,一字排开,从西向东依次编号为1, 2, 3, ……, n。每个山峰的高度都是不一样的。编号为i的山峰高度为hi。

小修从西往东登山。每到一座山峰,她就回头观望自己走过的艰辛历程。在第i座山峰,她记录下自己回头能看到的山峰数si。

何谓“能看到”?如果在第i座山峰,存在j<k<i,hj<hk,那么第j座山峰就是不可见的。除了不可见的山峰,其余的山峰都是可见的。

回家之后,小修把所有的si加起来得到S作为她此次旅行快乐值。现在n座山峰的高度都提供给你了,你能计算出小修的快乐值吗?

输入描述 Input Description

第一行一个整数n(n<=15000)。

第i+1(1<=i<=n)行是一个整数hi(hi<=109)。

输出描述 Output Description

仅一行:快乐值。

样例输入 Sample Input

5

2

1

3

5

9

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

说明:s1=0, s2=1, s3=2, s4=1, s5=1。

分析:

只用维护当前单调递减的山峰序列即可

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<stack>
 5 using namespace std;
 6 int n,a[15050],ans,s[15009],top=1;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)
11         scanf("%d",&a[i]);
12     s[1]=a[1];
13     for(int i=2;i<=n;i++)
14     {
15         ans+=top;
16         if(s[top]>a[i]) s[++top]=a[i];
17         else {
18             while(s[top]<=a[i]&&top>=1) 
19             {
20                 top--;
21             }
22             s[++top]=a[i];
23         }
24     }
25     printf("%d",ans);
26     return 0;
27 }

代码来源:http://www.cnblogs.com/suishiguang/p/6216847.html

 

相关文章
|
2天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
11 3
|
2天前
|
机器学习/深度学习 存储 算法
PHP中的数据结构及其在机器学习中的应用
本文探讨了PHP在机器学习中的作用,强调了数据结构的重要性。文中列举了PHP中的常见数据结构,如数组、对象、字典、链表、树和图,并解释了它们在机器学习场景下的应用。例如,数组用于特征向量,对象封装模型,字典存储特征映射,链表和树实现特定算法。通过示例代码展示了如何使用这些数据结构进行特征标准化和模型预测。文章总结指出,PHP的数据结构为机器学习提供了有效工具,随着技术发展,PHP在数据处理领域的应用将持续扩展。
14 4
|
2天前
数据结构初阶 栈
数据结构初阶 栈
7 1
|
7天前
|
存储 算法
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
7 0
|
7天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
9 0
|
7天前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
11 0
|
7天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
11 0
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
14 2
|
7天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
13 0
|
7天前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
9 0