P5331 [SNOI2019] 通信

$n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。 每个哨站 $i$ 需要选择以下二者之一： 1. 直接连接到控制中心，代价为 $W$； 2. 连接到前面的某个哨站 $j$ ($j

无

无

对于所有数据，$1 \leq n \leq 1000$，$0 \leq W,a_i \leq 10^9$。 对于 $10\%$ 的数据，$n \leq 10$； 对于另外 $10\%$ 的数据，$n \leq 20$； 对于另外 $20\%$ 的数据，$n \leq 50$，$W \leq 5$，$a_i \leq 4$； 对于另外 $20\%$ 的数据，$n \leq 100$； 对于另外 $20\%$ 的数据，$n \leq 300$； 对于余下 $20\%$ 的数据，无特殊限制。