P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower

    • 448通过
    • 2.4K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 高精 USACO
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    “逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀:

    "逢低吸纳,越低越买"

    这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好,看看你最多能按这个规则买几次。

    给定连续的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

    输入输出格式

    输入格式:

    第1行: N (1 <= N <= 5000), 表示能买股票的天数。

    第2行以下: N个正整数 (可能分多行) ,第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).

    输出格式:

    只有一行,输出两个整数:

    能够买进股票的天数和长度达到这个值的股票购买方案数量

    在计算方案的数量的时候,如果两个方案的股价序列相同,那么这样的两个方案被认为是相同的(只能算做一个方案)。因此,两个不同的天数序列可能产生同一个股价序列,这样只能计算一次。

    输入输出样例

    输入样例#1: 复制
    12
    68 69 54 64 68 64 70 67
    78 62 98 87
    输出样例#1: 复制
    4 2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。