【每日一题】3月24日Landscaping

题号 NC24444
名称 Landscaping
来源 USACO

题目描述

给你一个N个花坛现在你要对这N个花坛的泥土进行改造

第 $i$ 个花坛原来有 $a_i$ 单位的泥土

现在要求将每个花坛的泥土变成 $b_i$ 个单位

你可以进行如下操作

购买一个单位的泥土，花费 $x$ 元
去掉一个单位的泥土，花费 $y$ 元
从其他花坛 $j$ 移动一单位泥土，花费 $z * |i - j|$

问最小花费是多少？

样例

输入
4 100 200 1
1 4
2 3
3 2
4 0
输出
210

算法

(大根堆 + 反悔贪心)

这一题的思路还挺巧妙的

首先先将原序列 $a$ 处理一下

以样例为例： $a = {1,2,3,4} <==>A = {1,2,2,3,3,3,4,4,4,4}$

对于位置 $1$ 原来有 $1$ 单位土就往新数组加一个 $1$

对于位置 $2$ 原来有 $1$ 单位土就往新数组加两个 $2$

对于位置 $3$ 原来有 $3$ 单位土就往新数组加三个 $3$

对于位置 $4$ 原来有 $4$ 单位土就往新数组加四个 $4$

序列 $b$ 进行相同处理得到 $B = {1,1,1,1,2,2,2,3,3}$

那么现在的问题就变成了如何用最小的代价将序列 $A$ 变成序列 $B$

这就是一个经典的最短编辑距离问题

我们考虑用动态规划来求解

定义 $f[i] [j]$ 表示将序列只考虑序列 $A[1 ~ i]$ 的前 $i$ 转化为序列 $B[1 ~ j]$ 的最小操作花费是多少

状态计算：

边界情况：
1. $i = 0$ 时 $f[i] [j] = f[0] [j] = j * y$
2. $j = 0$ 时 $f[i] [j] = f[i] [0] = i* x$
通过购买一单位泥土将序列 $A$ 转化成序列 $B$ ,等价于将序列 $A[i]$ 转化成序列 $B[j - 1]$ 的最小花费 + $x$ ;

$f[i] [j] = min(f[i] [j - 1] + x)$
通过去掉一单位泥土将序列 $A$ 转化成序列 $B$ ,等价用 $y$ 去掉一单位土后，再将序列 $A[i - 1]$ 转化成序列 $B[j]$ 的最小花费;

$f[i] [j] = min(f[i + 1] [j] + y)$
如果 $A[i] == B[j]$ , $f[i] [j] = min(f[i - 1] [j - 1])$
如果 $A[i] != B[j]$ ，我们转移将位置 $B[j]$ 的泥土转移到 $A[i]$ 中, $f[i] [j] = min(f[i - 1] [j - 1] + z * |A[i] - B[j]|)$

状态计算5就体现了这种处理的好处，首先我们不会往 $B[j]$ 前面的花坛从找泥土转移，因为前面的泥土已经被处理好了

所以我们只能往后找，而我们观察 $B$ 序列里面的数是单调不减的所以最小距离就是|A[i] - B[j]|

时间复杂度是 $O(100N^2)$ 的，是不能解决本题的但是可以处理 $N <= 100$ 的数据

https://ac.nowcoder.com/acm/problem/24326

附上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 1010;
int x,y,z;
int f[N][N];
int a[N],b[N];
int A[N],B[N];
int n,m;

void solve()
{
    scanf("%d%d%d%d",&n,&x,&y,&z);
    for(int i = 1;i <= n;i ++) scanf("%d%d",&a[i],&b[i]);
    int cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 0;j < b[i];j ++)
            B[++ cnt] = i;
    }
    m = cnt;
    cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 0;j < a[i];j ++)
            A[++ cnt] = i;
    }
    n = cnt;
    memset(f,0x3f,sizeof f);
    for(int i = 0;i <= n;i ++) f[i][0] = y * i;
    for(int i = 0;i <= m;i ++) f[0][i] = x * i;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            f[i][j] = min(f[i - 1][j] + y,f[i][j - 1] + x);
            if(A[i] == B[j]) f[i][j] = min(f[i][j],f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j],f[i - 1][j - 1] + z * abs(A[i] - B[j]));
        }
    }
    printf("%d\n",f[n][m]);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

回到本题：

类似上面的我们只对每一个花坛的泥土，一个单位一个单位地处理

我们考虑一下这三种操作

当一个花坛的土比预期多的时候我们可以花 $y$ 将泥土去掉，或者转移

当一个花坛的土比预期多的时候我们可以花 $x$ 将购买，或者从其他花坛转移

我们似乎可以贪心的思考什么时候该转移什么时候该购买或者去掉

同样每一次我们只考虑前[1 ~ i]个花坛，且每一次只考虑一个单位泥土的操作，并且假设前面 $i - 1$ 个花坛都已经处理好了

当 $a_i > b_i$ 时，我们需要对第 $i$ 个花坛进行 $a_i - b_i$ 次操作

此时我们需要花费 $y$ 去掉这一单位泥土，或者向前面 $a_j < b_j$ 的花坛转移

设当前操作的花费是 $c_i$ ,则 $c_i = min(y,z * (i - j) - c_j)$ (减去 $c_j$ 是为了撤销上一次操作)

同理当 $a_i < b_i$ 时,我们从前面 $a_j > b_j$ 的花坛转移泥土过来,所以有 $c_i = min(x,z * (i - j) - c_j)$

观察式子 $c_i = min(y,z * (i - j) - c_j)$

我们可以变形一下: $c_i = min(y,z * i - (j * z+ c_j))$

对于 $i$ 来说 $z * i$ 是定值，对于 $j$ 来说 $j * z + c_j$ 是定值，并且当 $j * z +c_j$ 取最大时 $z * i - (j * z + c_j)$ 最小

所以我们可以用两个大根堆，一个维护 $a_j > b_j$ 的花坛的 $j * z + c_j$ 值，

另一个维护 $a_j < b_j$ 的花坛的 $j * z + c_j$ 值,

当 $c_i = z*i - (j * z + c_j)$ 时将 $(j * z + c_j)$ 从相应的堆中删去
然后累加所有 $c_i$ 就是答案

为什么这样贪心是对的

对于每个 $(j * z + c_j)$ （不变），将他分配给最近的 $i$ 是最优的
每次操作都是对前面阶段贪心的调整

具体证明可一看下面的参考

时间复杂度 $O(10Nlog(10N))$

参考文献https://blog.nowcoder.net/n/2905b1c8eb6346309b5c4c5222ec208c

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
int n;
LL x,y,z;

void solve()
{
    scanf("%d%lld%lld%lld",&n,&x,&y,&z);
    priority_queue<LL> heap1,heap2;
    LL res = 0;
    for(int i = 1;i <= n;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a < b)
        {
            for(int j = 0;j < b - a;j ++)
            {
                LL p = x;
                if(heap2.size())
                {
                    p = min(p,i * z - heap2.top());
                    heap2.pop();
                }
                res += p;
                heap1.push(i * z + p);
            }
        }
        if(a > b)
        {
            for(int j = 0;j < a - b;j ++)
            {
                LL p = y;
                if(heap1.size())
                {
                    p = min(p,i * z - heap1.top());
                    heap1.pop();
                }
                res += p;
                heap2.push(i * z + p);
            }
        }
    }
    printf("%lld\n",res);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(500);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}