旅游

题解

设 $f[i]$ 表示在第 $i$ 个感兴趣的城市卖艺的最少支出。

$$ f[i]=min(f[j]+\lceil \frac {c_i-c_j}{D} \rceil \ast a)-m_i $$

这个 $dp$ 是 $O(n^2)$ 的。

然后该往哪个方向思考呢？你注意到两个c同时+D相对关系还是不变。

设 $c_i=k_i \ast D+b_i$

原式可以变为：

$$ f[i]=min(f[j]+(k_i-k_j+\lceil \frac {b_i-b_j}{D} \rceil) \ast a-m_i) $$

只有 $b_i \gt b_j$ 才产生 $1$ 的贡献。所以，根据 $b$ 为下标维护线段树即可。