首页 > 技术文章 > N - Wifi Setup(单调队列优化dp)

UpMing 2021-04-10 21:14 原文

题目大意：

在坐标轴上给你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.

样例输入 Copy

样例输出 Copy

57.5

提示

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.

1
2

推荐阅读