题解

思路推导

只需考虑把每块木板增加 $0,1,2$ 个单位。因为在决定第 $i$ 块木板时，至多只有相邻木板的一个最终高度不能选择；三个候选高度 $a_i,a_i+1,a_i+2$ 中一定有可行者。若某个方案在这里使用了更大的增量，总能改成这三个候选之一而不增加费用。因此，全局最优解一定可以在每块木板的三个候选高度中取得。

设当前木板增加了 $j$ 个单位，其中 $j\in\{0,1,2\}$。相邻两块木板的最终高度不同正是唯一的转移限制，因此可以按木板从左到右进行动态规划。

做法

对每个询问维护三个状态。状态 $dp_j$ 表示处理到当前木板、当前木板增加 $j$ 个单位时的最小费用。

处理下一块木板时，枚举它的增量 $j$ 和上一块木板的增量 $k$。当 $a_{i-1}+k\ne a_i+j$ 时，可以从上一状态转移，并增加费用 $j\cdot b_i$。首块木板的三个状态分别初始化为 $0,b_1,2b_1$。

最终答案是最后一块木板三个状态的最小值。每个询问结束后重新初始化状态，询问之间互不影响。

正确性证明

首先，由三个连续候选高度中至多一个与前一块木板的最终高度相同可知，总存在增量不超过 $2$ 的合法选择。把任意使用更大增量的最优方案从左到右替换为不超过 $2$ 的合法选择，不会增加对应费用，因此一定存在每块增量均属于 $\{0,1,2\}$ 的最优方案。

动态规划枚举了当前与上一块木板的全部三个候选增量，并且只保留最终高度不同的转移，所以每条转移都保持已处理前缀美丽。反过来，任意增量均不超过 $2$ 的美丽方案在相邻位置都满足某条被枚举的转移，因而其费用会被纳入对应状态。取所有合法转移的最小值后，各状态就是相应条件下的最小费用。最后对末块的三个状态取最小值，得到全局最优费用。

复杂度分析

每块木板只进行常数次转移。单个询问的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$；所有询问合计的时间复杂度为 $O(\sum n)$。