Skip to content

1100: 投资大师

题目

题目描述

最近小韭菜又迷上了投资股票,通过请教一位投资大师,小韭菜被告知了未来T天内某只股票的走势,第i天的股票买入价为每股AP_i,第i天的股票卖出价为每股BP_i(数据保证对于每个i,都有AP_i>=BP_i),看上去他终于可以大赚一把了,但想薅羊毛可不容易。股票交易所规定第i天的一次买入至多只能购买AS_i股,一次卖出至多只能卖出BS_i股。

另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔W天,也就是说如果在第i天发生了交易,那么从第i+1天到第i+W天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过MaxP。

在第1天之前,小韭菜手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票。当然,T天以后,小韭菜想要赚到最多的钱。聪明的你,能帮助他大赚一笔吗?

输入格式

输入数据第一行包括3个整数,分别是T,MaxP,W。 接下来T行,第i行代表第i−1天的股票走势,每行4个整数,分别表示 AP_i,BP_i,AS_i,BS_i。

输出格式

输出数据为一行,包括1个数字,表示能赚到的最多的钱数。

样例输入

5 2 0

2 1 1 1

2 1 1 1

3 2 1 1

4 3 1 1

5 4 1 1

样例输出

3

数据范围

100%的数据,0<=W<T<=2000, 1<=MaxP<=2000。所有输入均为不超过2000的正整数。

时间限制:1s

空间限制:512MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!