Luogu P2900 [USACO08MAR]Land Acquisition G 题解

Describe

题目链接

Farmer John 准备扩大他的农场,眼前他正在考虑购买 $N$ 块长方形的土地。
如果 FJ 单买一块土地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地,他只需要支付 $5 \times 5=25$ 元, 比单买合算。
FJ 希望买下所有的土地。他发现,将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸,请你帮助他计算购买所有土地所需的最小费用。

Solution

考虑$dp$,但是怎么$dp$呢?
很显然,这需要先预处理。
将土地按照$w_i$从小到大排序,那么$l_i$筛选一下,一定是从大到小排序,否则肯定可以省略。
设$f_i$表示前$i$块土地的最小费用,那么有:$$f_i=min(f_j+w_{j+1}\times l_{i})(0\leq j <i)$$
显然,这个式子可以斜率优化。
设$0\leq j<k<i$且$k$比$j$优,则$$f_j+w_{j+1}\times l_{i}\leq f_k+w_{k+1}\times l_{i}$$
化简一下:
$$(f_j-f_k)+l_i\times (w_{j+1}-w_{k+1})\leq 0$$
即:
$$\frac{f_k-f_j}{w_{j+1}-w_{k+1}}\ge l_i$$
那么愉快的维护一个下凸壳即可。

Code

#include<bits/stdc++.h>
#define LD double
using namespace std;
int n,m,q[1000010],l,r;
long long f[100010];
struct node{int w,l;}a[1000010];
inline int cmp(node x,node y){return x.w>y.w||(x.w==y.w&&x.l>y.l);}
inline LD slope(int j,int k){
    return (LD)((LD)(f[k]-f[j]))/((LD)(a[j+1].w-a[k+1].w));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].l);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(a[i].l>a[m].l) a[++m]=a[i];
    l=r=1;q[1]=0;
    for(int i=1;i<=m;i++){
        while(l<r&&slope(q[l],q[l+1])<=a[i].l) l++;
        f[i]=f[q[l]]+1ll*a[i].l*a[q[l]+1].w;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld\n",f[m]);
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇