P3049 [USACO]园林绿化

$园林绿化$园林绿化

$Description$Description
有n块土地，每块有A[i]泥土，现把其改造成B[i]泥土，有3种操作：
(1)花费X向任意土地增加1泥土；
(2)花费Y向任意土地减少1泥土；
(3)花费Z*|i-j|把土地i的1泥土运到土地j。问最小花费是多少。

$A\left[i\right],B\left[i\right]\&lt;=100,n\&lt;=100,X,Y,Z\&lt;=1000$A[i],B[i]<=100,n<=100,X,Y,Z<=1000

$Solutio{n}_1$Solution1​

$最初想法$最初想法
思考发现, 最开始土地分为两种类型 : 要求降低, 要求升高.
在两个不同类型的土地 $i,j$i,j 之间, 若 $X+Y\&gt;Z\ast \mid i-j\mid$X+Y>Z∗∣i−j∣ 时, 则将泥土从 $i$i 搬往 $j$j 一定优于 直接升高降低.
于是按照此方法 贪心, 得到 $50pts$50pts.

$正解部分$正解部分
大概思想如上, 是因为我维护方法不对才拿了 $50pts$50pts, 重点看实现部分.

$实现部分$实现部分
对两种类型的土地分别建立两个 大根堆 $Q_1,Q_2$Q1​, Q2​, 内部元素是 单位泥土,
(可以理解为 $Q_1$Q1​ 是囤积的泥土, 可以堆到其他土地上; $Q_2$Q2​ 是筐, 可以将其他土地上的泥土倒到对应土地上),

从左往右边扫, 设当前位置为 $i$i, 土地类型为 要求下降, 即可以将当前泥土堆到其他土地上.
将该地泥土分为 $A\left[i\right]$A[i] 个单位泥土, 对每个单位泥土 单独处理,

对当前 要降低 的单位泥土, 有两种选择:

1. 直接扔泥土, $cost=X$cost=X, 此时需要 $Q_1.push(i\ast Z+X)$Q1​.push(i∗Z+X)
2. 从前方不同类型的土地 搬泥土, $cos{t}_2=i\ast Z-Q_2.top.first$cost2​=i∗Z−Q2​.top.first,
3. 从后方不同类型的土地 搬泥土,此时需要 $Q_2.push(i\ast Z+cos{t}_2)$ Q2​.push(i∗Z+cost2​)

注意以上都需执行 $Ans+=min(cost,cos{t}_2)$Ans+=min(cost,cost2​)., (弹出操作已省略).

时间复杂度 $O(N\ast 10\ast \log (N\ast 10\left)\right)$O(N∗10∗log(N∗10))
$Solutio{n}_2$Solution2​

可以使用 $Dp$Dp,
设 $F[i,j]$F[i,j] 表示 处理了 $i$i 个第一类型的单位泥土, $j$j 个第二类型的单位泥土 所花费的最小价值,

$F[i,j]=min\{\begin{array}{c}F[i-1,j]+X\\ F[i,j-1]+Y\\ F[i-1,j-1]+Z\ast \mid po{s}_i-po{s}_j\mid \end{array}$F[i,j]=min⎩⎪⎨⎪⎧​F[i−1,j]+XF[i,j−1]+YF[i−1,j−1]+Z∗∣posi​−posj​∣​

时间复杂度 $O\left(\right(N\ast 10{)}^2)$O((N∗10)2)

$Code$Code
贪心代码.

#include<bits/stdc++.h>
#define reg register

const int maxn = 105;
const int inf = 0x7f7f7f7f;

int N;
int X;
int Y;
int Z;
int Ans;
int A[maxn];
int B[maxn];

std::priority_queue <int> Q1;
std::priority_queue <int> Q2;

void Work_1(int i){  // In, Up
        int cost = inf;
        if(!Q1.empty()){
                int t = Q1.top();
                int tmp = i*Z - t;
                if(tmp < X) Q1.pop(), cost = tmp;
        }
        if(cost == inf) cost = X;
        Q2.push(i*Z + cost); Ans += cost;
}

void Work_2(int i){ // Out, Down
        int cost = inf;
        if(!Q2.empty()){
                int t = Q2.top();
                int tmp = i*Z - t;
                if(tmp < Y) Q2.pop(), cost = tmp;
        }
        if(cost == inf) cost = Y;
        Q1.push(i*Z + cost); Ans += cost;
}

int main(){
        scanf("%d%d%d%d", &N, &X, &Y, &Z);
        for(reg int i = 1; i <= N; i ++) scanf("%d%d", &A[i], &B[i]);
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 1; j <= abs(B[i]-A[i]); j ++)
                        if(A[i] < B[i]) Work_1(i); 
                        else Work_2(i);
        printf("%d\n", Ans);
        return 0;
}