P2900 [USACO08MAR]Land Acquisition G

洛谷传送门

Solution

发现对于一块土地 (x) 和 (y) ，如果 (l_ygeq l_x,h_ygeq h_x) ，那么把 (x) 和 (y) 合在一组对答案是不会更劣的。

将土地按照长度和宽度排序，维护一个栈，将有必要存在的土地留下。

在最优决策下，每一组土地都是连续的。因为如果有 (x,y,z) 三块连续土地，并且 (l_x<l_y<l_z,h_x>h_y>h_z) ，把 (x) 和 (z) 一组， (y) 自己一组，花费为 (h_xcdot l_z+h_ycdot l_y) ，三个一组花费是 (h_xcdot l_z) ，显然更优。

考虑DP。设 (f_i) 表示前 (i) 个土地的最小费用，易得： (f_i=min{f_i,f_{j}+h_{j+1}cdot l_{i}}) ，但是时间复杂度为 (O(n^2)) ，过不去，考虑优化。

用斜率优化。设 (k=h_{j+1},b=f_j) ，那么直线为 (y=kx+b) ，那么之前的转移方程就相当于求 (x=l_i) 时的 (y_{min})

Code

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;
const int N=5e4+10;
int n,a[N],b[N],f[N],q[N],hd,tl,stk[N],top;
struct node{
    int a,b;
    bool operator < (const node &x) {
        return a==x.a?b<x.b:a<x.a;
    }
}p[N];

inline int slope(int p,int t){
    return f[p]+a[t]*b[p+1];
}

inline bool cross(int t1,int t2,int i){
    return 1ll*(f[t1]-f[t2])*(b[i+1]-b[t1+1])<1ll*(f[i]-f[t1])*(b[t1+1]-b[t2+1]);
}

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].a,&p[i].b);
    sort(p+1,p+n+1);
    stk[++top]=1;
    for(int i=2;i<=n;i++){
        while(top&&p[i].b>=p[stk[top]].b) --top;
        stk[++top]=i;
    }
    n=top;
    for(int i=1;i<=n;i++) a[i]=p[stk[i]].a,b[i]=p[stk[i]].b;
    hd=tl=0;
    for(int i=1;i<=n;i++){
        while(hd<=tl&&slope(q[hd],i)>slope(q[hd+1],i)) ++hd;
        f[i]=f[q[hd]]+a[i]*b[q[hd]+1];
        while(hd<=tl&&cross(q[tl],q[tl-1],i)) --tl;
        q[++tl]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}