BZOJ 1597: [Usaco2008 Mar]土地购买 – [DP/斜率优化][模版]


题目传送门(BZOJ)
>原文链接<

题解 :

斜率优化模版题

有关斜率优化原理及讲解,请参见我这篇博客

  1. 分析

    土地顺序是没有用的,考虑排个序方便我们做,先按长度降序,长度一样的按宽度降序。

    对于某块土地,如果有一块既比他长又比他宽,他就没用了, 因为肯定可以在买走那块的同时不花费代价的买走这块。

    我们把这样的都扔掉:维护一个当前宽度最大值,由于长度是降序的,后面的都比前面的短,如果宽度还不能超过最大值的话,那它就是没用的,扔掉就行。

  2. 斜率优化

    然后就有了个DP方程,设F[i]为买到第i块地的最小代价,长度为x,宽度为y

    那么转移就是F[i] = min{F[j]+x[j+1]\times y[i]} 。其中$0\le j < i$ $F$ 单调递增,$x$ 单调递减,$y$ 单调递增。可以斜率优化。 定义$F[j]$为$b$, $x[j+1]$为$k$,$y[i]$ 为$x$ 。 当队首更新不优于队首第二个更新,弹掉队首 更新$F[i]$

    i构成的直线与队尾直线交点在队尾与队尾第二个元素构成的焦点右边,弹掉队尾。

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define K(i) (a[i+1].x)
#define B(i) (f[i])
#define Y(i, j) (f[j]+(ll)a[j+1].x*a[i].y)
struct Node {
    int x, y;
    bool operator < (const Node &A) const {
        return x ==A.x ? y > A.y : x > A.x;
    }
}a[51000], b[51000];
ll f[51000];
int q[51000], l, r;
bool cmp(int r, int r_1, int i) {
    return ((ll)B(r)-B(i))*(K(i)-K(r_1)) <= ((ll)B(r_1)-B(i))*(K(i)-K(r));
}
signed main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &b[i].x, &b[i].y);
    sort(b+1, b+n+1);
    int mxy = 0, cnt = 0;
    for(int i = 1; i <= n; i ++ ) if(b[i].y > mxy) {
        a[++cnt] = b[i], mxy = b[i].y;
    }
    memset(f, 0x3f, sizeof f); f[0] = 0;
    n = cnt; 
    for(int i = 1; i <= n; i ++ ) {
        while(l Y(i, q[l+1])) l ++ ;
        f[i] = Y(i, q[l]);
        while(l

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注