题意 : 有n块地皮，每块有A[i]泥土，现把其改革成B[i]泥土，有3种操纵：(1)花费X向任意地皮增加1泥土；(2)花费Y向任意地皮减少1泥土；(3)花费Z*|i-j|把地皮i的1泥土运到地皮j。问最小花费是几多。
分析 :
参考了洛谷大神们给出的思路，下面简述一下
简单的讲就是对付每一个点，先将其花费必然的价值使得其数量
酿成 B[i] 泥土，但是这个花费不必然是最优的，可以通过后期调解
来到达使得花费更小，调解的方案固然就是对付转变前后缺少和
转变前后增加这两种地皮来进行考虑，对付缺少的地皮，可以考虑
直接花费 X 的价钱去买地皮，也可以考虑从先前转变前后增加的土
地花费 Z 转移过来。对付转变前后增加的地皮，也是差不久不多的情况
先界说 opt(x) 代表当前点暂时的最优取值，即最小花费
举个例子，若当前第一个点是转变前后缺少的，那么由于还没有枚举到
转变前后增加的点，所以只能通过花费 X 的方案来使得其转变前后相等
即 opt(first_point) = (B[first_point] - A[first_point])*X ==> 固然，这只是暂时的
for( 凭据下标从小到到大枚举每一个点 ) :
若当前转变前后的地皮差值不乱 continue
若当前转变前后地皮是缺少的 :
假设当前点是 j ，且之前有 i1、i2、i3…… 是转变前后增加的
若选择通过从从这些 i 来转移到 j 使得转变前后相等
则有 (j-i1)*Z - opt(i1)、(j-i2)*Z - opt(i2)、(j-i3)*Z - opt(i3)…… 固然要从这些取最小
考虑一下为什么是样子，因为是从 i 转移而来，所以之前 i 孕育产生的最优花费，我们该当是要减失的
以此来抵消失之前 i 的花费，使得其转移到 j 这里来，，孕育产生越发优秀的方案，不理解就往下看
简化一下有 j*Z - max[i + opt(i)] ==> 从那么多个 i 中取最大的，才华保证花费最小
故最后 opt(j) = min( X, j*Z - max[i + opt(i)] ) ==> 固然还要和直接采办这种方案取一个 min
若转变前后地皮是增加的 :
和缺少的情况很像，就非论述了
ans += opt(j)
上面就是 伪代码思路 这个贪心显而易见是正确的，不停从多种方法取最优
这种贪心思路很容易想到，就是不知道怎么去用代码写出来，或者没有一个清晰的思路
这种先确定一个值，后面再去调解取更优的贪心思路，学习一下
至于DP的思路，其实我没看过，有空再说
#include<bits/stdc++.h> #define LL long long using namespace std; LL N, X, Y, Z; priority_queue<LL> opt_lack;///暗示每一个缺少点的最优取值 priority_queue<LL> opt_surplus;///暗示每一个多余点的最优取值 int main(void) { while(~scanf("%lld %lld %lld %lld", &N, &X, &Y, &Z)){ while(!opt_lack.empty()) opt_lack.pop(); while(!opt_surplus.empty()) opt_surplus.pop(); LL before, after, ans = 0; for(LL j=1; j<=N; j++){ scanf("%lld %lld", &before, &after); if(before == after) continue; if(before < after){ for(LL i=1; i<=after-before; i++){ if(opt_surplus.empty() || j*Z - opt_surplus.top() >= X){ ans += X; opt_lack.push(j*Z+X); }else{ LL T = opt_surplus.top(); opt_surplus.pop(); ans += j*Z - T; opt_lack.push(j*Z + j*Z - T); } } }else{ for(LL i=1; i<=before-after; i++){ if(opt_lack.empty() || j*Z - opt_lack.top() >= Y){ ans += Y; opt_surplus.push(j*Z+Y); }else{ LL T = opt_lack.top(); opt_lack.pop(); ans += j*Z - T; opt_surplus.push(j*Z + j*Z - T); } } } } printf("%lld\n", ans); } return 0; }
View Code洛谷 P3049 Landscaping ( 贪心 || DP)
标签：
原文地点：https://www.cnblogs.com/Rubbishes/p/8901562.html