TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1330
  • 题目
  • P1330低价购买
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(<=231-1),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。
    这里是某支股票的价格清单:
    日期 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

    输入格式

    第1行: N (1<=N<=5000),股票发行天数
    第2行: N个数,是每天的股票价格。

    输出格式

    输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。由于方案数很大,你需要输出它mod 109+7的值。

    样例输入

    12
    68 69 54 64 68 64 70 67 78 62 98 87 

    样例输出

    4 2

    提示

    注意读清题,此题的求解是求存在的符合条件的解,所有的而不是单纯的n的个数;


    来源  感谢nodgd铲除题目中一个巨大的坑