投球游戏

题目描述

有一个投球游戏，玩法是将球投到 $N$ 个篮筐里。具体玩法如下：

投篮顺序必须同时符合以下三个规则：

例如给出的 $3$ 个篮筐距离和顺序为 $130\ 200\ 55$。

规则一：

第一次投篮可以投任意一个篮筐；

规则二：

从第二次投篮开始，每一次投篮只能投顺序在上一次篮筐的后面的篮筐；

如果第一次投的 $200$ 篮筐，那么接下来就不能投 $130$ 的篮筐，可以投 $55$ 的篮筐。

规则三：

从第二次投篮开始，每一次投篮只能投比上一次投篮距离更近的篮筐。

如果第一次投的 $130$ 的篮筐，那么接下来不能投 $200$ 的篮筐，只能投 $55$ 的篮筐。

现给出 $N$ 的数值，和 $N$ 个篮筐的距离及顺序，假定每次投篮都能投进，请你编写程序计算按照投球规则最多能投进几个球。

如：$N=3$，$3$ 个篮筐的距离及顺序为：$130\ 200\ 55$

按照三条规则，一共有以下三种投球方案：

1）如果第一次投 $130$，那么投 $130$，$55$，最多可以投进 $2$ 球；

2）如果第一次投 $200$，那么投 $200$，$55$，最多可以投进 $2$ 球；

3）如果第一次投 $55$，那么投 $55$，最多可以投进 $1$ 球。

则按照规则最多可投进 $2$ 球。

输入格式

第一行输入一个正整数 $N$（$2<N<20$），表示篮筐的个数。

第二行分别输入 $N$ 个正整数（$10<$ 正整数 $<1000$）并以一个空格隔开，分别表示篮筐距离和 $N$ 个篮筐顺序，每个篮筐的距离都不相同。

输出格式

输出一个整数，表示最多能投进球的个数。

样例输入 #1

3
130 200 55

样例输出 #1

2

数据范围

$2<N<20$；篮筐距离为大于 $10$ 且小于 $1000$ 的正整数，且各篮筐距离互不相同。

知识点与难度

本题涉及的知识点从属于 GESP六级（动态规划基础、线性DP），难度等级：⭐⭐⭐。

测试点分布