P3049 [USACO]园林绿化

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

$A[i],B[i]<=100,\n<=100,\X,Y,Z<=1000$

$mathcal{Solution_1}$

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

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

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

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

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

直接扔泥土, $cost=X$ , 此时需要 $Q_1.push(i*Z + X)$
从前方不同类型的土地 搬泥土, $cost_2 = i*Z-Q_2.top.first$ ,
从后方不同类型的土地 搬泥土,此时需要 $Q_2.push(i*Z+cost_2)$

注意以上都需执行 $Ans += min(cost,cost_2)$ ., (弹出操作已省略).

时间复杂度 $O(N*10*log(N*10))$
$mathcal{Solution_2}$

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

$F[i, j]= minegin{cases} F[i-1, j] + X\ F[i, j-1] + Y\ F[i-1,j-1]+Z*∣pos_i-pos_j∣ end{cases}$

时间复杂度 $O((N*10)^2)$

$mathcal{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
", Ans);
        return 0;
}