问题2151--股票交易（HDU3401）

2151: 股票交易（HDU3401）

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

预测未来T 天的股市。在第i 天可以以APi 的价格购买一只股票，或者以BPi 的价格卖出一只股票。在第i 天最多买ASi 只股票，最多卖BSi 只股票。两个交易日的间隔应大于W天。也就是说，假设在第i 天交易（任何买卖股票都被视为交易），则下一个交易日必须是第（i +W +1）天或更晚。在任何时候都不可以拥有超过maxP 只股票。
第1天之前，小明已经有了无限多的钱，但没有股票，他想从股票市场尽可能多地赚钱。

输入

第1行是一个整数t ，表示测试用例的数量。每个测试用例的第1行都是三个整数T、 maxP、W ，0≤W <T ≤2000，1≤maxP≤2000。接下来的T 行各有4个整数APi 、BPi 、ASi 、BSi ，1≤BPi≤APi ≤1000，1≤ASi ，BSi ≤maxP 。

输出

单行输出小明赚得最多的钱数。

样例输入 Copy 

1
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

样例输出 Copy 

3

来源/分类

动态规划算法 单调队列 
[提交] [状态]