logo AlgoBeat OnlineJudge
登录 注册

#101578. [BZOJ 1578] [Usaco2009 Feb]Stock Market 股票市场

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

题目描述

尽管奶牛们天生谨慎,她们仍然在住房抵押信贷市场中受到打击,现在她们开始着手于股市。 Bessie 很有先见之明,她不仅知道今天 只股票的价格,还知道接下来一共 天的(包括今天)。给定一个 天的股票价格矩阵以及初始资金 ,求最优买卖策略使得总获利最大化。每次必须购买股票价格的整数倍,同时你不需要花光所有的钱(甚至可以不花)。考虑这个牛市的例子(这是 Bessie 最喜欢的)。在这个例子中,有 只股票和 天。奶牛有 的钱来投资。

股票 今天的价格 明天的价格 后天的价格

以如上策略可以获得最大利润:第一天买入第一只股票。第二天把它卖掉并且迅速买入第二只,此时还剩下 的钱。最后一天卖掉第二只股票,此时一共有 的钱。

输入格式

第一行:三个空格隔开的整数:

行:第 行包含了第 只股票第 天的价格

输出格式

第一行:最后一天卖掉股票之后最多可能的钱数。

样例

样例输入 #1

2 3 10
10 15 15
13 11 20

样例输出 #1

24

数据范围与提示

对于 的数据,

约定你的获利不超过 。 Usaco 2009 Feb Gold