Lugou2900 土地征用

未分类

考虑对于 $(a,b)$ 的土地如果有 $(c,d)$ 的土地满足 $a\leq c$ 与 $b \leq d$，$(a,b)$ 将不会对答案产生任何贡献。所以将这些土地删去。最后留下的土地序列按 $a$ 排序后一定 $a$ 递增，$b$ 递减。这样子每次最优d的决策一定是连续的区间，方程为 $f(i)=\max\limits_{0\leq j <i} \{f(j)+a_i\times b_{j+1}\}$ ，斜率优化即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long LL;
#define int LL
const int MAXN = 5e4;
int n, tail, l, r;
int dp[MAXN | 1], q[MAXN | 1];
struct Land {
  int a, b;
  friend bool operator< (const Land &lhs, const Land &rhs) {
    return (lhs.a < rhs.a) || (lhs.a == rhs.a && lhs.b > rhs.b);
  }
} a[MAXN | 1], s[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline double slope(int x, int y) {
  return 1.0 * (dp[y] - dp[x]) / (s[x + 1].b - s[y + 1].b);
}
signed main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i].a = read();
    a[i].b = read();
  }
  std::sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) {
    while (tail > 0 && s[tail].b <= a[i].b) --tail;
    s[++tail] = a[i];
  }
  l = 1;
  r = 1;
  for (int i = 1; i <= tail; ++i) {
    while (l < r && slope(q[l], q[l + 1]) <= s[i].a) ++l;
    int j = q[l];
    dp[i] = dp[j] + s[i].a * s[j + 1].b;
    while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) --r;
    q[++r] = i;
  }
  printf("%lld\n", dp[tail]);
  return 0;
}