P2900 [USACO08MAR] Land Acquisition G

传送门

思路:

先将土地按照长\(H\)排序
从后往前遍历如果有出现\(H[i] \le H[j]\ \text{and}\ W[i] \le W[j]\)则这块土地是没有贡献的(\(i\)与\(j\)拼单)
处理完之后H从小到大有序, W从大到小有序
方程:
\(f[i] = f[j - 1] + max(h[k]) * max(w[k]) (k∈[j, i])\)
等价于
\(f[i] = f[j - 1] + h[i] * w[j];\)
将式子变成
\(f[j - 1] = -h[i] * w[j] + f[i];\)
\(y = k x + b\)
\(f[j - 1]\) 表示 \(y\)
$-h[i] $表示 \(k\)（斜率）
\(w[j]\)表示\(x\)
\(f[i]\)表示\(b\)

解题步骤:

1. 算出\(x, y\)
2. 用单调队列维护下凸包
   拿队尾两个元素组成线段的斜率与\(i\)和队尾的元素组成的线段的斜率比较
   如果\(i\)和队尾的元素组成的线段的斜率大，则出队

bool check(int i, int j, int k) // i是最右边的点，j是队列倒数第二个点，k是队尾
{
    return (y[k] - y[j]) * (x[i] - x[k]) <= (y[i] - y[k]) * (x[k] - x[j]);
}

3. 入队
4. 比较队首元素和队首第二个元素分别与 \(i\)算出的值进行比较
   若队首元素算出的值不优于队首第二个元素的值，则出队

while (hd < tl && clac(i, q[hd]) >= clac(i, q[hd + 1]))
    ++hd;

5. 算出\(\text{dp}\)的值

代码：

无优化\(\text{dp}\):

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 5e4 + 5;
int n, f[N], vis[N], len;

struct Node
{
    int h, w;
    friend bool operator< (Node x, Node y)
    {
        if (x.h != y.h) return x.h < y.h;
        return x.w > y.w;
    }
}a[N], b[N];

signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld", &a[i].h, &a[i].w);
    sort(a + 1, a + 1 + n);
    int maxx = 0;
    for (int i = n; i >= 1; --i)
    {
        if (maxx >= a[i].w) vis[i] = 1;
        maxx = max(maxx, a[i].w);
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) b[++len] = a[i];
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= len; ++i)
        for (int j = 0; j < i; ++j)
            f[i] = min(f[i], f[j] + b[i].h * b[j + 1].w);
    printf("%lld", f[len]);
    return 0;
}

正解:

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 5e4 + 5;
int n, m, f[N], vis[N], q[N], hd, tl, x[N], y[N];

struct Node
{
    int h, w;
    friend bool operator< (Node x, Node y)
    {
        if (x.h != y.h) return x.h < y.h;
        return x.w > y.w;
    }
}a[N], b[N];

int clac(int i, int j)
{ return f[j - 1] + b[i].h * b[j].w; }

bool check(int i, int j, int k)
{ return (y[k] - y[j]) * (x[i] - x[k]) <= (y[i] - y[k]) * (x[k] - x[j]); }

signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld", &a[i].h, &a[i].w);
    sort(a + 1, a + 1 + n);
    int maxx = 0;
    for (int i = n; i >= 1; --i)
    {
        if (maxx >= a[i].w) vis[i] = 1;
        maxx = max(maxx, a[i].w);
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) b[++m] = a[i];
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    hd = 1, tl = 0;
    for (int i = 1; i <= m; ++i)
    {
        x[i] = b[i].w, y[i] = f[i - 1];
        while (hd < tl && check(i, q[tl - 1], q[tl])) --tl;
        q[++tl] = i;
        while (hd < tl && clac(i, q[hd]) >= clac(i, q[hd + 1])) ++hd;
        f[i] = clac(i, q[hd]);
    }
    printf("%lld\n", f[m]);
    return 0;
}