Codeforces 1083E The Fair Nut and Rectangles
题目链接
https://codeforces.com/contest/1083/problem/E
题目大意
给你一个 $n$ 个左下角和右上角为 $(0, 0)$ 和 $(x_i, y_i)$ 的矩形，每个矩形有一个权值 $a_i$。问选出若干个矩形，最大化这些矩形的面积并与这些矩形的权值和的差。限制条件为，没有嵌套的矩形
题目分析
从限制条件中可以得知，任何两个矩形，横坐标大的那个纵坐标一定小，，反之亦然，且没有坐标相同的两个矩形。由此可以想到，首先对所有的矩形按照横坐标由小到大排序。之后考虑使用 $DP$ 来解决这道题。则可以推出递推式
$$f[i] = max\{f[j] – x_i y_j + x_i y_i – a[i]\} (1 \leq j < i)$$
但是此时时间复杂度是 $O(N ^ 2)$ 的。问题在于，每个新的矩形加入的时候 $x_i$ 都会影响递推式中的 $x_i y_i$ 这项与 $j$ 矩形有关的项。但注意到，$f[j] – x_i y_j$ 事实上是个一次的函数，后面有关 $i$ 矩阵的项为定值，因此可以考虑使用斜率优化。令 $y = (-y_j)x + (f[j])$，那么 $f[i]$ 的最大取值即为前面所有直线以及 $y = 0$ 直线中，在 $x = x_i$ 处取值最大的直线所对应的矩阵所转移来的。由于所有的直线的斜率具备单调性，可以使用双端队列来维护，求解即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, t;
long long ans = 0;
struct ex {
long long x;
long long y;
long long a;
};
ex p[maxn];
struct queue {
long long k[maxn];
long long b[maxn];
int l, r;
double getp(long long ka, long long ba, long long kb, long long bb){
return (double)(bb - ba) / (double)(ka - kb);
}
int push(long long kk, long long bb){
while(r - l + 1 > 1 and getp(k[r], b[r], kk, bb) > getp(k[r - 1], b[r - 1], k[r], b[r])){
r--;
}
r++;
k[r] = kk;
b[r] = bb;
return 0;
}
int pop(long long x){
while(r - l + 1 > 1 and k[l] * x + b[l] < k[l + 1] * x + b[l + 1]){
l++;
}
return 0;
}
long long front(long long x){
if(r - l + 1 <= 0){
return 0;
}
return k[l] * x + b[l];
}
queue(){
r = 0, l = 1;
}
};
queue q;
long long read(){
long long x;
scanf("%lld", &x);
return x;
}
bool cmp(ex x, ex y){
return x.y > y.y;
}
int main(){
int i, j;
long long tmp;
n = read();
for(i=1;i<=n;i++){
p[i].x = read();
p[i].y = read();
p[i].a = read();
}
sort(p + 1, p + n + 1, cmp);
for(i=1;i<=n;i++){
q.pop(p[i].y);
tmp = q.front(p[i].y) + p[i].x * p[i].y - p[i].a;
tmp = max(tmp, p[i].x * p[i].y - p[i].a);
ans = max(ans, tmp);
q.push(-p[i].x, tmp);
}
printf("%lld\n", ans);
return 0;
}