P3062 [USACO12DEC] Wifi Setup S

Farmer John’s $N$ cows ($1 \le N \le 2000$) stand at various positions along a straight path, which we can regard as a one-dimensional number line. Since his cows want to stay in email contact with each other, FJ plans to install Wifi base stations at positions of his choosing so that all cows have wireless coverage. The cost of a Wifi base station depends on its transmission distance: a base station with power $r$ costs $A + B \times r$, where $A$ is the fixed installation cost and $B$ is the cost per unit distance. If a base station is installed at position $x$, it provides coverage to any cow located in the interval $[x - r, x + r]$. A base station with $r = 0$ is allowed, but it only covers a cow located exactly at $x$. Given $A$, $B$, and the locations of FJ’s cows, determine the minimum total cost to provide wireless coverage for all cows. Base stations may be placed at any real position on the line.

- Line 1: Three space-separated integers $N$, $A$, $B$, where $1 \le N \le 2000$ and $0 \le A, B \le 1000$. - Lines $2$ to $N + 1$: Each line contains an integer in $[0, 1{,}000{,}000]$ describing the location of one cow.

- Line 1: The minimum total cost to provide wireless coverage to all cows.

There are $3$ cows at positions $7$, $0$, and $100$. Installing a base station of power $r$ costs $20 + 5 \times r$. An optimal solution is to build one base station at position $3.5$ (power $r = 3.5$) and another at position $100$ (power $r = 0$). The first base station covers cows $1$ and $2$, and the second covers cow $3$. Translated by ChatGPT 5