#P17879. Best Trades Again
Best Trades Again
这是 All the Trades Are the Best 的另一个版本。本题中,每个工作区间都有自己的交易次数限制,所有工作区间都位于同一天内,不保证工作区间随机生成。
一天分为 个等长时段,第 个时段的股价为 。
给定 个工作区间。第 个区间从时段 开始,在时段 结束,包含两个端点,且 。在这个区间内,你最多可以完成 次交易。
一次交易包含买入一股股票,然后在严格更晚的时段卖出,利润为卖出价格减去买入价格。你同一时刻最多持有一股股票,因此再次买入之前必须先卖出当前持有的股票。
所有买卖都必须在当前工作区间内发生,并符合时间顺序。你也可以不进行交易,此时利润为0。
对每个工作区间独立求出能够获得的最大总利润。
输入格式
第一行两个整数 ,分别表示一天的时段数和工作区间数。
第二行 个整数 ,表示各时段的股价。
接下来 行,每行三个整数 ,表示工作区间及其允许的最大交易次数。
数据范围:
- ;
- ;
- ;
- 。
工作区间和交易次数限制均无随机性保证。
输出格式
输出 行,第 行一个整数,表示第 个工作区间内的最大总利润。
样例
6 7
3 1 4 1 5 9
1 6 1
1 6 2
1 6 3
2 5 1
2 5 2
4 4 0
1 6 0
8
11
11
4
7
0
0
样例说明
第一次询问可以在时段2买入,在时段6卖出,利润为 。
第二次询问可以在时段2买入、时段3卖出,再在时段4买入、时段6卖出,总利润为 。第三次询问虽然允许多一次交易,但最大利润仍为11。
第六、七次询问的 ,不允许交易,答案为0。