正题

题目链接:https://www.luogu.com.cn/problem/P2900

---

题目大意

$n$块$h_i\ast w_i$的土地，购买一组土地需要$max(h)\ast max(w)$，求购买所有土地的最小费用。

---

解题思路

首先如果$h$和$w$都小于另一块土地显然是不需要的，去掉后我们可以得到一个$h$递减，$w$递增的序列
设$f_i$表示并购到第$i$个时最小费用，有转移$$f_i=min\{f_j+h_{j+1}\ast w_i\}$$
比较两个决策$$f_j+h_{j+1}\ast w_i<f_k+h_{k+1}\ast w_i$$
$$f_j-f_k<w_i\ast (h_{k+1}-h_{j+1})$$
$$\frac{f_j-f_k}{h_{k+1}-h_{j+1}}<w_i$$

然后斜率优化时间复杂度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; struct node{ll h,w; }a[N]; ll n,f[N],q[N]; bool cmp(node x,node y) {return (x.h==y.h)?(x.w>y.w):(x.h>y.h);} double slope(ll x,ll y) {return 1.0*(f[x]-f[y])/(a[y+1].h-a[x+1].h);} int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&a[i].h,&a[i].w);sort(a+1,a+1+n,cmp);ll p=1;for(ll i=1;i<=n;i++)if(a[i].w>a[p].w)a[++p]=a[i];n=p;ll l=1,r=1;q[1]=0;for(ll i=1;i<=n;i++){while(l<r&&slope(q[l],q[l+1])<=a[i].w)l++;f[i]=f[q[l]]+a[q[l]+1].h*a[i].w;while(l<r&&slope(q[r-1],q[r])>=slope(q[r-1],i))--r;q[++r]=i;}printf("%lld",f[n]); }

总结

以上是生活随笔为你收集整理的P2900-[USACO08MAR]Land AcquisitionG【斜率优化】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。