【每日一题】3月24日Landscaping

题号 NC24444
名称 Landscaping
来源 USACO

题目描述

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

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

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

你可以进行如下操作

1. 购买一个单位的泥土，花费元
2. 去掉一个单位的泥土，花费元
3. 从其他花坛移动一单位泥土，花费

问最小花费是多少？

样例

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

算法

(大根堆 + 反悔贪心)

这一题的思路还挺巧妙的

首先先将原序列处理一下

以样例为例：

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

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

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

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

序列进行相同处理得到

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

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

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

定义表示将序列只考虑序列的前转化为序列的最小操作花费是多少

状态计算：

1. 边界情况：

   1. 时
   2. 时

2. 通过购买一单位泥土将序列转化成序列,等价于将序列转化成序列的最小花费 + ;

   

3. 通过去掉一单位泥土将序列转化成序列,等价用去掉一单位土后，再将序列转化成序列的最小花费;

   

4. 如果,

5. 如果，我们转移将位置的泥土转移到中,

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

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

时间复杂度是的，是不能解决本题的但是可以处理的数据

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;
}

回到本题：

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

我们考虑一下这三种操作

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

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

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

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

当时，我们需要对第个花坛进行次操作

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

设当前操作的花费是,则 (减去是为了撤销上一次操作)

同理当时,我们从前面的花坛转移泥土过来,所以有

观察式子

我们可以变形一下:

对于来说是定值，对于来说是定值，并且当取最大时最小

所以我们可以用两个大根堆，一个维护的花坛的值，

另一个维护的花坛的值,

当时将 从相应的堆中删去
然后累加所有就是答案

为什么这样贪心是对的

1. 对于每个（不变），将他分配给最近的是最优的
2. 每次操作都是对前面阶段贪心的调整

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

时间复杂度

参考文献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;
}