OpenJudge

28:Buy low, Buy lower plus

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

萌主要买股票了,

大家都知道“逢低吸纳”是炒股的一条成功秘诀。

萌主想成为一个成功的投资者,来找你帮忙。要求你每次购买股票时的股价一定要比你上次购买时的股价低.

按照这个规则购买股票的次数越多越好,看看你最多能按这个规则买几次。

给定连续的N天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次购买时的股价低。写一个程序,求出最多能买几次股票。

以下面这个表为例, 某几天的股价是:

天数 1 2 3 4 5 6 7 8 9 10 11 12

股价 68 69 54 64 68 64 70 67 78 62 98 87

这个例子中, 聪明的投资者(按上面的定义),如果每次买股票时的股价都比上一次买时低,那么他最多能买4次股票。一种买法如下(可能有其他的买法):

天数 2 5 6 10

股价 69 68 64 62

当然萌主大人不会让你这么容易通过的,必须使用高精度~~(抖S的萌主伤不起)

输入
第1行: N (1 <= N <= 5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ,第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).
输出
只有一行,输出两个整数:D S
其中,D表示能够买进股票的天数
S表示长度达到这个值的股票购买方案数量
在计算方案的数量的时候,如果两个方案的股价序列相同,那么这样的两个方案被认为是相同的(只能算做一个方案)。因此,两个不同的天数序列可能产生同一个股价序列,这样只能计算一次。
样例输入
12
68 69 54 64 68 64 70 67
78 62 98 87
样例输出
4 2
提示
数据范围:

对于40%的数据 1 <= N <= 20
对于80%的数据 1 <= N <= 1000
对于100%的数据 1 <= N <= 5000

额外hint:对于90%的数据 1 <= S <= 10^18
全局题号
6515
添加于
2013-11-04
提交次数
37
尝试人数
9
通过人数
1