P3062 [USACO12DEC] Wifi Setup S

Farmer John 的 $N$ 头奶牛（$1 \le N \le 2000$）都站在从谷仓到牧场的直线路径上的不同位置，我们可以将其视为一条一维数轴。由于他的奶牛喜欢通过电子邮件保持联系，FJ 希望在不同位置安装无线基站，以便所有奶牛都能获得无线覆盖。 经过一番比较，FJ 了解到无线基站的成本取决于其传输距离：一个功率为 $r$ 的基站成本为 $A + B \times r$，其中 $A$ 是安装基站的固定成本，$B$ 是每单位传输距离的成本。如果 FJ 在位置 $x$ 安装这样的设备，那么它可以向位于 $x - r$ 到 $x + r$ 范围内的任何奶牛传输数据。允许安装传输功率 $r = 0$ 的基站，但这只能覆盖位于基站同一位置的奶牛。 给定 $A$ 和 $B$ 的值，以及 FJ 奶牛的位置，请确定 FJ 为所有奶牛提供无线覆盖的最小成本。

- 第一行：三个空格分隔的整数 $N, A, B$（$0 \le A, B \le 1000$）。 - 第 $2$ 到第 $1+N$ 行：每行一个在 $0$ 到 $1\,000\,000$ 范围内的整数，表示一头奶牛的位置。

- 一行：为所有奶牛提供无线覆盖的最小成本。

有三头奶牛，位置分别为 $7, 0$ 和 $100$。安装一个功率为 $r$ 的基站成本为 $20 + 5r$。 最优方案是在位置 $3.5$ 处建造一个功率为 $3.5$ 的基站，在位置 $100$ 处建造一个功率为 $0$ 的基站。第一个基站覆盖奶牛 $1$ 和 $2$，第二个基站覆盖奶牛 $3$。