P5331 [SNOI2019] Communication

There are $n$ sentry stations arranged in a line. The frequency band of station $i$ is $a_i$. Each station $i$ needs to choose one of the following two options: 1. Connect directly to the control center, with a cost of $W$. 2. Connect to some previous station $j$ ($j

The first line contains two non-negative integers $n, W$, representing the number of sentry stations and the cost to connect to the control center. The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ separated by spaces, representing the frequency band of each station in order.

Output one line containing one non-negative integer, representing the answer.

For all testdata, $1 \leq n \leq 1000$, $0 \leq W, a_i \leq 10^9$. For $10\%$ of the testdata, $n \leq 10$. For another $10\%$ of the testdata, $n \leq 20$. For another $20\%$ of the testdata, $n \leq 50$, $W \leq 5$, $a_i \leq 4$. For another $20\%$ of the testdata, $n \leq 100$. For another $20\%$ of the testdata, $n \leq 300$. For the remaining $20\%$ of the testdata, there are no special constraints. Translated by ChatGPT 5