题目大意：
在坐标轴上给你n个点，让求覆盖这n个点的最小价值
价值的计算方法为A+B*r ，r为线段的半径（可以为0）
n<=1000
题目思路：
首先一种O(n^2)的解法
设dp[i]为覆盖前i个点的最小价值
我们计算dp[i]的时候已经知道了dp[1---i-1]的答案，
那我们枚举[1,i]的一个点j，然后在j-i重新布置一个检测器
得到转移方程
dp[i] = dp[j] + val
for(int i = 1 ; i <= n ; i++)
{
ll temp = 1e18;
for(int j = 1 ; j <= i ; j++)
{
ll t = dp[j - 1] ;
ll r = (a[i] - a[j]) ;
ll s = 2 * A + B * r ;
t = t + s;
if(t < temp) temp = t;
}
dp[i] = temp;
}
View Code我们继续观察这个转移方程
dp[i]是由最小的dp[j] + val 转移来的
val的计算公式是
(a[i] - a[j])*B + A*2
那么这个式子可以写成
dp[j-1] +(a[i] - a[j])*B + A*2
每次插入的数字是a[i] ，我们需要向前找一个最小的dp[j-1] + a[j]*B (相同的部分可以不看)
这样就可以用单调队列优化，存储一个单调上升的值（上述式子）
然后每次插入i的时候，我们取队头来计算
CODE:
ll n, a[3000], A, B;
ll dp[3000];
ll l, r, q[3002];
ll cal(ll x)
{
return dp[x - 1] - B * a[x];
}
int main()
{
cin >> n >> A >> B;
l = 1, r = 0;
rep(i, 1, n) a[i] = read();
sort(a + 1, a + 1 + n);
for(int i = 1 ; i <= n ; i++)
{
while(l <= r && cal(i) <= cal(q[r]) )r--;
q[++r] = i;
ll id = q[l];
dp[i] = dp[id - 1] + 2ll * A + B * (a[i] - a[id]);
}
cout << dp[n] / 2ll;
if(dp[n] % 2) cout << ".5";
return 0 ;
}
View Code
题目描述：
Farmer John‘s N cows (1 <= N <= 2000) are all standing at various positions along the straight path from the barn to the pasture, which we can think of as a one-dimensional number line. Since his cows like to stay in email
contact with each-other, FJ wants to install Wifi base stations at various positions so that all of the cows have wireless coverage.
After shopping around, FJ learns that the cost of a Wifi base station depends on distance it can transmit: a base station of power r costs A + B*r, where A is a fixed cost for installing the base station and B is a cost per unit of transmission distance. If FJ installs such a device at position x, then it can transmit data to any cow located in the range x-r ... x+r. A base station with transmission power of r=0 is allowed, but this only provides coverage to a cow located at the same position as the transmitter.
Given the values of A and B, as well as the locations of FJ‘s cows, please determine the least expensive way FJ can provide wireless coverage for all his cows.
输入
* Line 1: Three space-separated integers: N A B (0 <= A, B <= 1000).
* Lines 2..1+N: Each line contains an integer in the range 0..1,000,000 describing the location of one of FJ‘s cows.
输出
* Line 1: The minimum cost of providing wireless coverage to all cows.
提示
There are 3 cows at positions 7, 0, and 100. Installation of a base station of power r costs 20 + 5*r.The optimal solution is to build a base station at position 3.5 (with power 3.5) and another at position 100 (with power 0). The first base station covers cows 1 and 2, and the second covers cow 3.
N - Wifi Setup(单调队列优化dp)
原文：https://www.cnblogs.com/UpMing/p/14642144.html
