#C241008E. [USACO08MAR] Land Acquisition G

标签（Label）

斜率优化
动态规划

网址（Website）

P2900 [USACO08MAR] Land Acquisition G - 洛谷

练习题： #C241008B. PolarSea与IOI

题解（Solution）

首先观察题目性质。

想最小化费用，如果出现矩形 $a$ 和 $b$ 满足 $a.x\le b.x$ 且 $a.y\le b.y$ ，那么将这两个矩形放在一组中小的那个一定没有贡献，因此，我们可以直接预处理删除所有满足上述条件的小的矩形；
最后形成的矩形一定是一个类似逆序对的形式，排序后发现，在 $a.x$ 变大的时候， $a.y$ 一定变小，而我们的分组肯定是将此时相邻的分在一起更优，考虑 $\mathrm{dp}$ 。

令 $f_i$ 表示选到了第 $i $ 个矩形的最小费用，则 $f_i = \min_{j=0}^{i-1}\{f_j + a[i].x\times a[j+1].y\}$ ，化简可得时间复杂度 $O(n^2)$ 转化得 $f_j= -a[i].x\times a[j+1].y\ +\ f_i$ ，对应 $y=k\times x+b$ ，用斜率优化 $\mathrm{dp}$ ，发现 $-a[i].x$ 是不断变小的，$a[j+1]$ 不断变小，据此可以画出大概的图像，分析可得我们需要维护一个下凸包的单调队列，具体的操作是：

如果尾部斜率 $k\ge -a[i].x$ ，弹出，直到 $k<-a[i].x$ ；
令 $j$ 为队尾 $q[tail]$ ，通过方程计算得到当前的 $f_i$ ；
要加入的新点为 $(a[i+1].y,\ f_i)$ ，据此判断队首元素是否更优：如果队首斜率 $k$ 小于等于点 $(a[i+1].y,\ f_i)$ 与队首组成的线的斜率，弹出队首。

最后输出答案 $f_n$ 即可。

时间复杂度 $O(n\log n)$ ，瓶颈竟然在最开始的排序。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

int n;
P a[N]; 

int f[N];
inline double cal(int i,int j){
	return 1.0*(f[i]-f[j])/(a[i+1].y-a[j+1].y);
}int q[N], hd=0, tl=1;

void solve(){
	n = rd();For(i,1,n) a[i] = {rd(),rd()};
	sort(a+1,a+n+1,[](P x, P y){return x.x==y.x ? x.y<y.y : x.x<y.x;});
	{
		stack<P> st;
		For(i,1,n){
			while(st.size() && a[i].y>=st.top().y) 
				st.pop();
			st.push(a[i]);
		}n = st.size();
		while(st.size()){
			a[st.size()] = st.top();
			st.pop();
		}
	}//去掉包含的情况
	
	For(i,0,n){//注意！！！要从0状态转移
		while(hd>tl && cal(q[tl],q[tl+1])>=-a[i].x) tl++;
		int j = q[tl];f[i] = f[j] + a[i].x*a[j+1].y;
		while(hd>tl && cal(q[hd],q[hd-1])<=cal(i,q[hd])) hd--;
		q[++hd] = i;
	}
	printf("%lld\n",f[n]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}