简要题意

• 小 Rei 在 $n$ 天内每天骑共享单车，第 $i$ 天 $s_i$ 分钟，每分钟费用 $c$ 元
• 可任意购买 $m$ 种骑行卡，其中第 $i$ 种骑行卡：
• 售价为 $w_i$ 元，在有效期 $d_i$ 天内每天前 $t_i$ 分钟免费
• 同一天多张卡有效时，取免费时间的最大 $t_i$
• 求最小总开销
• 数据范围：$n,t \le 150$

区间 DP？

• 每张骑行卡会在一个区间的时间内产生影响，自然可以想到区间 DP
• 考虑最优方案中 $t_i$ 最小的骑行卡 $i$，设这张卡在第 $x$ 天购买。接着可以把 $n$ 天分成三段：$[1,x-1],\,[x,x+w_i-1],\,[x+w_i,n]$，这三段分别成为相对“独立”的子问题
• 但是独立性不一定成立：可能存在其他的骑行卡的有效时间与上述的至少两段时间都有交，这样就不是独立的子问题了

构造独立性

• 我们假设存在一个 $t_j > t_i$ 的骑行卡 $j$，其有效时间为 $[y,y+w_j-1]$，满足 $y\le x \le y+w_j-1$。此时可以舍弃卡 $i$ 与 $[y,y+w_j-1]$ 有交的部分时间而不影响答案
• 也就是只要将卡 $i$ 的有效期限定为 $\le w_i$ 的任意整数值，同时不允许后续的有效期区间跨过卡 $i$ 有效期边界，就能分成三个独立的子问题

区间 DP

• 接着就可以做区间 DP，设 $f[i][j][k]$ 表示只考虑时间 $i,i+1,\cdots,j$ 与路程中超过 $k$ 分钟的部分，最小的代价是多少。转移只需要枚举区间内的最小 $t$ 以及左右端点，就能做到 $O(n^4 t^2)$
• 为了时间复杂度与 $m$ 无关，可以预处理 $\mathrm{cost}_{i,j}$ 表示有效期为 $i$ 免费时间为 $j$ 的最少骑行卡价格

DP 优化

• 转移中需要枚举区间中的最小 $t_i$，实际上是在求后缀最大值，在加入辅助数组优化后做到 $O(n^4t)$
• 注意到转移时需要同时枚举中间区间的左右端点。我们考虑再设计一个中间状态，将转移中的枚举左右端点分成两步，就能做到 $O(n^3t)$
• 区间 DP 自带 $1/3!=1/6$ 的常数，$150^3/6\approx 8\times 10^7$ 可以在时限内通过