#11553. 投球游戏【蓝桥杯】

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

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

如给出 3 个篮筐距离和顺序为 130 , 200 , 55 。

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

  • 第一次投篮可以投任意一个篮筐。

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

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

  • 从第二次投篮开始,每一次投篮只能投比上一次投篮距离更近的篮筐(投小于上一次投篮距离的篮筐)。 如果第一次投的 130 的篮筐,那么接下来不能投 200 的篮筐,只能投 55 的篮筐。

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

输入格式

第一行输入一个正整数 N (2 < N < 20) 表示篮筐的个数。

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

输出格式

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

样例

【样例 1 输入】

3
130 200 55

【样例 1 输出】

2

【样例 1 解释】

N = 3 ,3 个篮筐的距离及顺序为:130 , 200 , 55 。

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

  • 如果第一次投 130 ,那么投 130 , 55 ,最多可以投进 2 球。

  • 如果第一次投 200 ,那么投 200 , 55 ,最多可以投进 2 球。

  • 如果第一次投 55 ,那么投 55 ,最多可以投进 1 球。

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

数据范围与提示

十二届蓝桥杯C++国赛试题 E