codeforces 1083E The Fair Nut and Rectangles 动态规划 单调性优化

题意

给出n个长方形，每个长方形有一个权值，要求选其中一些长方形，使得面积并减去权值和最大化

题解

首先 $dp$dp方程很好想
$dp\left[i\right]=max\left\{dp\right[j]+y_i\ast (x_i-x_j)-a_i\}$dp[i]=max{dp[j]+yi​∗(xi​−xj​)−ai​}
由于是 $n^2$n2复杂度，所以需要优化，变形后
$dp\left[i\right]=max\{-x_j\ast y_i+dp[j\left]\right\}+x_i\ast y_i-a_i$dp[i]=max{−xj​∗yi​+dp[j]}+xi​∗yi​−ai​
化成直线

每新加入一条直线，都要维护这个下凸
出现下面情况时，绿线应该被删除

依据是，蓝绿的交点在绿红交点的右侧，说明绿线永远不会用上
$-k_1\ast x+b_1=-k_2\ast x+b_2$−k1​∗x+b1​=−k2​∗x+b2​
$x=\frac{b_1-b_2}{k_1-k_2}$x=k1​−k2​b1​−b2​​

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;
struct node{
	LL x,y,v;
	bool operator < (const node z) const{
		return x<z.x;
	}
}a[N];
LL d[N];
int q[N],h,t;

LL cal(int i,int j){
	return d[j]+a[i].y*(a[i].x-a[j].x)-a[i].v;
}

double spy(int i,int j){
	return (double) (d[i]-d[j])/(a[i].x-a[j].x);
}

int main(){
	int n;
	sc(n);
	for (int i=1;i<=n;i++)
		scanf("%I64d%I64d%I64d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+n+1);
	LL ans=0;
	for(int i=1;i<=n;i++){
		while(h<t && cal(i,q[h])<cal(i,q[h+1])) h++;
		d[i]=cal(i,q[h]); ans=max(ans,d[i]);
		while(h<t && spy(i,q[t])>spy(q[t],q[t-1])) t--;
		q[++t]=i;
	}
	cout<<ans;
}