CF1083E 题解
$\text{Description}$
给定 $n$ 个左下角在 $(0,0)$，四边与 $x,y$ 轴平行的矩形（以右上角顶点的形式给出），保证两两不包含，每个矩形有一个权值 $a_i$，试选出若干个矩形，使得其面积并减去权值和最大。
$1\le n\le 10^6,1\le x_i,y_i\le 10^9,0\le a_i\le x_iy_i$
$\text{Solution}$
考虑两两不包含的含义，即我们将这些顶点按横坐标升序排列后，其纵坐标单调递减。
那么，我们按如上顺序将矩形加入决策集，可以发现其增加的面积只与上一个加入决策集的矩形相关，因此可以动态规划。
设 $f_i$ 表示最后一个选取了第 $i$ 个矩形的决策集中最大的答案，则有
注意到后者是两变量的乘积项，所以考虑斜率优化，考虑用 $j$ 转移 $i$ 时，有：
将 $f_j$ 看作 $y$，将 $x_j$ 看作 $x$，则 $y_i$ 为斜率，我们要最大化截距。
因此，我们考虑维护一个上凸壳，也即相邻两点连线斜率单调递减，那么套路性地，我们需要找到与下一点连线的斜率最大但小于 $y_i$ 的点，该点即最优决策点。
回到问题本身，注意到 $y_i$ 单调递减，则可用单调队列维护上凸壳，每次转移时先从队首弹出与下一点连线的斜率比 $y_i$ 大的点，然后取队首作为决策点，最后在插入该点时删去不符合条件的决策点即可。
时间复杂度 $\mathcal O(n\log n)$，瓶颈在于排序。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
#define REG register
using namespace std;
typedef long long ll;
typedef double D;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
const int N=1000005;
int n;
struct Rec{ll x,y,a;}rec[N];
inline bool cmp(Rec u,Rec v){return u.x<v.x;}
ll F[N];
inline ll Calc(int i,int j){return F[j]+rec[i].y*(rec[i].x-rec[j].x)-rec[i].a;}
inline D Slp(int i,int j){return 1.0*(F[i]-F[j])/(rec[i].x-rec[j].x);}
int Q[N],head=1,tail;
inline void Work(){
read(n);
for(REG int i=1;i<=n;++i)
read(rec[i].x),read(rec[i].y),read(rec[i].a);
sort(rec+1,rec+n+1,cmp);
F[1]=rec[1].x*rec[1].y-rec[1].a;
Q[++tail]=0;
for(REG int i=1;i<=n;++i){
while(head<tail&&Slp(Q[head],Q[head+1])>=rec[i].y) ++head;
F[i]=Calc(i,Q[head]);
while(head<tail&&Slp(Q[tail-1],Q[tail])<Slp(Q[tail],i)) --tail;
Q[++tail]=i;
}
ll Mx=0;
for(REG int i=1;i<=n;++i) Mx=max(Mx,F[i]);
printf("%lld\n",Mx);
}
int main(){Work();}
|
