解题思路

本题需要在“出租仓库赚日租金 m”与“买入‐持有‐卖出赚价差（每次买/卖各付一次运费 k）且占用仓库、期间无法出租”之间做最优切换。允许多次交易，且同一天不能买入又卖出。

将问题建模为二维状态动态规划（DP），每天结束时仅关心两种状态：

• dp0：第 i 天结束时仓库空闲（未持有货物）能获得的最大收益

  • 若今天保持空闲并出租：dp0 + m
  • 若今天从持有转为空闲（今日卖出）：dp1 + (price[i] - k)（卖出日不可出租）

题目内容

小伊家里有一个仓库库房，库房可以出租给别人使用，每日租金价格是固定为 $m$ 元,另一方面，最近一段时间小伊拿到了一种商品未来 $n$ 天的价格，于是想倒卖该商品赚差价，选择合适的日期买入，然后占用自己的库房储存，再选择合适的日期卖出以获取最大收益，

买卖商品当天和存放商品期间仓库不可出租，买一次或卖一次的运输成本为k元，假定除买卖当天和存放商品期间之外的所有日期每天都稳定可以出租出去。不存在同一天买入又卖出的情况。

输入描述

输入都是数字

第一行$m$($0<m<1$万)

第二行$k$($0<k<1$万)

第三行$n$($0<n<1$万)

第四行 $n$ 个数字代表未来 $n$ 天每一天的商品交易价格($0$<每天的商品交易价格<$1$亿)

输出描述

$n$天后的收入最大值。

补充说明

不限制先买入再卖出的交易次数。

小伊本金充足，不考虑挣够本金再买入商品，允许一开始就买入商品。

样例1

输入

10
30
7
100 200 120 110 100 400 500

输出

400

说明 日租金收入 $m=10$ ，商品运费 $k=30$ ，未来 $7$ 天商品价格变化：$100$ $200$ $120$ $110$ $100$ $400$ $500$ ，则未来 $7$ 天最大收益为 $400$ 。

计算过程如下：

第一天买入商品，第二天卖出商品，占用两天仓库，获得商品倒卖收益 $200-100-30*2=40$ ；

第三天和第四天仓库末占用，出租获得收益 $10*2=20$ ；

第五天买入商品，第七天卖出商品，占用三天仓库，获得商品倒卖收益 $500-10030*2=340$ ;

因此未来七天可获得最大收益为 $40+20+340=400$ 。输出为 $400$ ；