bzoj1597 斜率优化dp

思路：先把没有用的土地去掉，然后按照x轴排序，容易得到dp转移方程

dp[ i ] = min{ dp[ j ] + b[ j + 1 ] * a[ i ] }    0 <= j < i

典型的斜率优化。

#include<bits/stdc++.h>
#define LL long long
#define ll long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg

using namespace std;

const int N = 2e5 + 7;
const int M = 1e7 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;

struct node {
    LL x, y;
    node(LL x = 0, LL y = 0) {
        this->x = x;
        this->y = y;
    }
    bool operator < (const node &rhs) const {
        if(x == rhs.x) return y < rhs.y;
        return x < rhs.x;
    }
} a[N];

int n, tot, head, rear, stk[N];
LL dp[N];

bool check1(int id1, int id2, LL c) {
    return dp[id2] - dp[id1] <= c * (a[id1 + 1].y - a[id2 + 1].y);
}

bool check2(int id1, int id2, int id3, int id4) {
    return (dp[id4] - dp[id3]) * (a[id1 + 1].y - a[id2 + 1].y) <= (dp[id2] - dp[id1]) * (a[id3 + 1].y - a[id4 + 1].y);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i].x, &a[i].y);
    }
    sort(a + 1, a + 1 + n);
    tot = 1;
    for(int i = 2; i <= n; i++) {
        while(tot && a[i].y >= a[tot].y) tot--;
        a[++tot] = a[i];
    }
    n = tot;

    dp[0] = 0;
    stk[++rear] = 0;

    for(int i = 1; i <= n; i++) {
        while(rear > head && check1(stk[head], stk[head + 1], a[i].x)) head++;
        int id = stk[head];
        dp[i] = dp[id] + a[id + 1].y * a[i].x;
        while(rear > head && check2(stk[rear - 1], stk[rear], stk[rear], i)) rear--;
        stk[++rear] = i;
    }
    printf("%lld
", dp[n]);
    return 0;
}


/*
*/