2328. 魔法森林的“防空泡泡枪”挑战
1000ms
256MB
简单
贪心算法
题目描述
在宁静的魔法森林里,松鼠哈利研发出了一种名为“防空泡泡枪”的防御系统,专门用来拦截敌方投下的“臭气弹”。
不过,这种泡泡枪有一个非常傲娇的限制:
1. **高度衰减**:每一套泡泡枪系统拦截的第一发臭气弹可以是任意高度。
2. **后劲不足**:但是,一旦开始工作,该系统以后拦截的每一发臭气弹的高度都**不能高于**前一发的高度。
3. **固定顺序**:臭气弹是按时间顺序一个接一个飞来的,顺序不可改变。
现在,森林雷达捕捉到了敌军投下的 $n$ 个臭气弹的高度。请你帮哈利算一算,如果要拦截所有的臭气弹,最少需要配备多少套这样的“防空泡泡枪”系统?
输入格式
- 第一行包含一个正整数 $n$ ($1 \le n \le 500$),表示臭气弹的总数。
- 第二行包含 $n$ 个正整数,依次表示每个臭气弹的高度。每个高度不超过 $30000$。
输出格式
- 输出一个整数 $k$,表示最少需要的系统套数。
样例 1
输入 (Input)
6 389 207 300 200 310 65
输出 (Output)
3
样例说明
- **样例说明**:
臭气弹高度序列为:`389, 207, 300, 200, 310, 65`。
- 第一套系统:拦截 `389`, `207`, `200`, `65`(高度依次递减或相等)。
- 第二套系统:拦截 `300`。
- 第三套系统:拦截 `310`。
共需 3 套系统。
- 对于 $100\%$ 的数据:$1 \le n \le 500$,高度 $\le 30000$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功