普及-⏱ 1000ms💾 256MB#P3172🏷️ 动态规划

题目描述

塔防游戏里有一座拦截塔,它的第一发拦截弹可以打到任意高度, 但此后每一发拦截弹的高度都不得高于前一发。敌方的飞行单位按先后顺序进入射程, 高度依次为 $h_1, h_2, \ldots, h_N$;每个单位必须在其进入顺序上被一发拦截弹对应击落。

只有一座塔,求它最多能击落多少个单位。

输入格式

第一行一个整数 $N$; 第二行 $N$ 个整数,为各单位依次进入时的高度,用空格分开。

输出格式

一行,一个整数:最多能击落的单位数。

数据范围

$$1 \le N \le 15$$
,高度为不超过 $30000$ 的正整数。

样例输入 #1
8
389 207 155 300 299 170 158 65
样例输出 #1
6
样例输入 #2
1
100
样例输出 #2
1