题解【土地征用_USACO08MAR】(洛谷P2900)

题意

需要购买\(n\)块土地，每块土地有一个长\(r_i\)与宽\(c_i\)。可以将这些土地打成几包购买。每包土地的价格为这包土地中最大的长乘以最大的宽。求最小花费。

分析一下

• \(DP\)没话说，看数据范围知道要用斜率优化了。
• \(F_i\)表示处理完第\(i\)块土地的最小花费。
• 转移就是枚举之前的一块土地\(j\)，将\([j + 1\cdots i]\)全部看成一包进行转移，即：
  \[F_i = min\{F_j + r_{j+1} \cdot c_i\}\]
• 这个转移成立的前提是\(c\)数组要从小到大排序，才能在转移时\(c_i\)最大。
• 再有就是预先把那些直接被包含的土地（长与宽都小于其他任意一块土地）删掉，买了也对转移没用。

优化过程

• 啊啦斜率优化原理什么的不太清楚啦~
• 只知道按步骤来不怎么会错啦~

1. 设状态\(i\)，有两种转移\(j,k\)，且\(j < k < i\)且\(k\)更优。即：
   \[F_k + r_{k + 1} \cdot c_i < F_j + r_{j + 1} \cdot c_i\]
2. 移项，变为左边与\(i\)有关的不等式：
   \[c_i \cdot (r_{k+1} - r_{j + 1}) < F_j - F_k\]
   \[\because r_{k + 1} \geq r{j + 1}\]
   \[\therefore c_i < \frac{F_j - F_k}{r_{k + 1} - r_{j + 1}}\]
3. 所以只有满足上面这个不等式才能保证\(k\)比\(j\)更优。
4. 维护一个单调队列。队首维护时间，只有当队首与队首\(+1\)不满足于上面那个不等式时，证明队首不比第二个优，队首就可以出队了。
5. 此时队首一定是最优的，用这个队首来更新答案。（就相当于原来的转移方程枚举\(j\)的过程）
6. 队尾维护单调性。当新加入一个元素\(i\)时，将队列最后两个值代入不等式的右边而得出的值与队尾和\(i\)代入不等式的右边得出的值比较，如果右边小于左边，说明\(i\)比队尾更优，则将队尾踢出。（与题面中求最小值一致）
7. 将\(i\)加入队列。

• 对于每个元素，共进队一次，出队一次，时间复杂度\(O(n)\) 。

代码君

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 50005;
struct Earth {
    long long r, c;
    bool operator < (const Earth &res) const {return c < res.c;}
} ar[MAXN], a[MAXN]; //结构体，ar为踢去没用的土地后的数组。 
int n, N;
long long f[MAXN];
int head, tail, que[MAXN * 5];

inline double g(int j, int k) {
    return (f[j] - f[k]) / (ar[k + 1].r - ar[j + 1].r);
} //将不等式的右边写成函数。 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].r, &a[i].c);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        while (N && ar[N].r <= a[i].r)
            N--; //如果宽比前面的大（排序决定），长也比前面大，就将前面的踢出（单调栈）。 
        ar[++N] = a[i];
    }
    head = tail = 0;
    que[0] = 0, /*队列里存放的是数组下标*/f[0] = 0;
    for (int i = 1; i <= N; i++) {
        while (head < tail && ar[i].c >= g(que[head], que[head + 1]))
            head++; //维护时间 
        f[i] = f[que[head]] + ar[que[head] + 1].r * ar[i].c; //更新答案 
        while (head < tail && g(que[tail - 1], que[tail]) >= g(que[tail], i))
            tail--; //维护单调性 
        que[++tail] = i; //加入元素 
    }
    printf("%lld\n", f[N]);
    return 0;
}

题解【土地征用_USACO08MAR】(洛谷P2900)

原文：https://www.cnblogs.com/JackHomes/p/9467006.html