P2900 [USACO08MAR]Land Acquisition G

P2900 [USACO08MAR]Land Acquisition G

如果存在矩形 $i, j$ 使得 $h _ i \le h _ j \wedge w _ i \le w _ j$ ，那么矩形 $i$ 一定不选。对所有矩形排序，双指针删除这样的矩形 $i$ ，剩下的一定满足 $\forall i < j, w _ i \le w _ j \wedge h _ i \ge h _ j$ ，显然一些 $h, w$ 相近的矩形同时选择更优。对于现在排序好的序列，即将其划分为若干部分一起选择。则有
$$
f _ i = \min _ {j < i} \{f _ j + w _ i h _ j + 1\}
$$
显然可以斜率优化。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e4 + 10;
const LL inf = 1e16;
int n, m;
int hd = 1, tl, q[N];
LL f[N];
PII w[N], v[N];
double slp(int a, int b)
{
    return (double)(f[a] - f[b]) / (double)(v[a + 1].first - v[b + 1].first);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i].first, &w[i].second);
    sort(w + 1, w + n + 1);
    for (int i = n; i; i--)
        if (v[m].second < w[i].second)
            v[++m] = w[i];
    q[++tl] = 0;
    for (int i = 1; i <= m; i++)
    {
        while (hd < tl && slp(q[hd], q[hd + 1]) > -v[i].second)
            hd++;
        f[i] = f[q[hd]] + (LL)v[q[hd] + 1].first * v[i].second;
        while (hd < tl && slp(q[tl], q[tl - 1]) < slp(q[tl], i))
            tl--;
        q[++tl] = i;
    }
    printf("%lld", f[m]);
    return 0;
}