CF1083E 题解

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$

斜率优化

概论

斜率优化是一种优化 1D/1D 动态规划的方法。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×