CF1083E The Fair Nut and Rectangles

给定 $n$ 个平面直角坐标系中左下角为坐标原点，右上角为 $(x_i,\ y_i)$ 的互不包含的矩形，每一个矩形拥有权值 $a_i$ 。你的任务是选出若干个矩形，使得选出的矩形的面积并减去矩形的权值之和尽可能大。输出最大值。

$1\leq n\leq10^6,\ 1\leq x_i,\ y_i\leq10^9,\ 0\leq a_i\leq x_i\cdot y_i$

斜率优化

因为所有矩阵互不包含，所以先按 $x_i$ 升序， $y_i$ 降序排个序

令 $f_i$ 为，截止第 $i$ 个矩阵，选取任意个矩阵所能得到的最大值

则： $$f_i=\displaystyle\max_{j<i}{f_j+S_i-S_i\cap S_j-a_i}$$

因为 $x_i$ 升序， $y_i$ 降序，所以 $$f_i=\displaystyle\max_{j<i}{f_j+x_iy_i+x_jy_i-a_i}$$

接着套路地化式子，得到 $$f_j=y_ix_j+f_i+a_i-x_iy_i$$

令 $Y=f_j,\ K=y_i,\ X=x_j$ ，因为 $y_i$ 单调递减，所以直接维护即可

时间复杂度 $O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

#define nc getchar()

typedef long long ll;

typedef long double db;

const int maxn = 1e6 + 10;

ll f[maxn];

int n, q[maxn];

struct node {

  ll x, y, w;

  bool operator < (const node& o) const {

    return y > o.y;

  }

} a[maxn];

inline ll read() {

  ll x = 0;

  char c = nc;

  while (c < 48) c = nc;

  while (c > 47) x = (x << 3) + (x << 1) + (c ^ 48), c = nc;

  return x;

}

db slope(int x, int y) {

  return a[x].x == a[y].x ? 1e18 : db(f[x] - f[y]) / db(a[x].x - a[y].x);

}

int main() {

  n = read();

  for (int i = 1; i <= n; i++) {

    a[i].x = read();

    a[i].y = read();

    a[i].w = read();

  }

  ll ans = 0;

  int l = 1, r = 1;

  sort(a + 1, a + n + 1);

  for (int i = 1; i <= n; i++) {

    while (l < r && slope(q[l], q[l + 1]) > a[i].y) l++;

    f[i] = f[q[l]] + (a[i].x - a[q[l]].x) * a[i].y - a[i].w;

    while (l < r && slope(q[r - 1], q[r]) < slope(q[r], i)) r--;

    q[++r] = i, ans = max(ans, f[i]);

  }

  printf("%I64d", ans);

  return 0;

}

orz $\color{black}{S}\color{red}{ooke}$

秒客网

CF1083E The Fair Nut and Rectangles

相关文章