自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:08:37，当前版本为作者最后更新于2020-06-24 14:30:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P5244 题解

宣传博客

题意

二维坐标系中，选择坐标严格递增的一些点，相邻点依次作为对角线组成的长方形面积和最小。

$$x_0<x_1<...<x_k$$ $$y_0<y_1<...<y_k$$

这个应该很容易理解

解答

二维最长不下降序列？
按$x$排序，一维$LIS$

$DP$!
假设$p$的最长上升序列长度为$i$，枚举点$p$左下角的所有最长上升序列长度为$i-1$的点$q$

那么我们可以写出转移方程：

$$dp_p=\min_{q∈L_{i-1}\ |\ p>>q}\{dp_q+(x_p-x_q)(y_p-y_q)\} $$

其中$p>>q$表示$p$在$q$的左上方，$L_x$表示以$x$结尾的$LIS$长度。

那么我们按层$dp$
一共有$S$层
对于$L_i$里的所有点
决策：要在$L_{i-1}$里选一个点，选哪个？
约束：这个点要在左下方

简化问题：
没有约束？
对于点$p_1,p_2∈L_i$，$q_1,q_2∈L_{i-1}$，
$X_{p_1}<X_{p_2} -> Y_{p_1}>Y_{p_2}$
$X_{q_1}<X_{q_2} -> Y_{q_1}>Y_{q_2}$

可以证明： 如果$p_1$选择了$q_1$，那么$p_2$一定选择$q_1$

但是这样肯定不能AKIOI，于是我们要优化。
这里就会用到一个常见的手段：$\color{red}{决策单调性！}$

有约束，怎么办？中国山东找蓝翔
我们发现约束也是连续的！
因此当我们求区间最优解的时候，可以用$Segment\ tree$来维护。
线段树每个结点表示$L_{i-1}$的一段区间。

所以我们确定步骤：

1. 对于第$i$层的一个点，找到$L_{i-1}$线段树上所有包含的区间，这些结点上记录下能对该点进行转移。
2. 每个结点上记录了一些$L_i$的转移目标，这些转移目标符合单调性。
3. 遍历$L_{i-1}$这棵线段树的所有（可转移的）结点，更新$L_i$的$DP$值。

代码军

此处借鉴了dalao$\text{\color{red}LIdox1536513344}$的代码
线段树建树

inline void buildSegTr(int &rt,int l,int r){
  rt=++size;
  a[rt].ls=a[rt].rs=0;
  a[rt].trans.clear();
  if(l==r)return;
  int mid=(l+r)>>1;
  buildSegTr(a[rt].ls,l,mid);
  buildSegTr(a[rt].rs,mid+1,r);
}

转移

inline void Modify(int rt,int l,int r,int x){
	if(p[x].x>=p[point[r]].x&&p[x].y>=p[point[l]].y){
		a[rt].trans.push_back(x);
		return;
	}
	if(p[x].x<=p[point[l]].x||p[x].y<=p[point[r]].y) return;
	int mid=(l+r)>>1;
	Modify(a[rt].ls,l,mid,x);
	Modify(a[rt].rs,mid+1,r,x);
}

解决问题

inline void Solve(int l,int r,int ql,int qr){
	ll ans=inf,from=0;
	int mid=(l+r)>>1,now=tmp[mid];
	for(int i=ql;i<=qr;++i){
		int pos=point[i];
		ll res=dp[pos]+1ll*(p[now].x-p[pos].x)*(p[now].y-p[pos].y);
		if(res<ans){
			ans=res;
			from=i;
		}
	}
	dp[now]=min(dp[now],ans);
	if(l<mid) Solve(l,mid-1,from,qr);
	if(mid<r) Solve(mid+1,r,ql,from);
}
inline void Work(int rt,int l,int r){
	if(a[rt].trans.size()){
		tmp=a[rt].trans;
		Solve(0,tmp.size()-1,l,r);
	}
	if(l==r) return;
	int mid=(l+r)>>1;
	Work(a[rt].ls,l,mid);
	Work(a[rt].rs,mid+1,r);
}

主函数怎么用

sort(p+1,p+n+1,cmpx);
for(ll i=1;i<=n;++i){
	ly[i]=Query(p[i].y)+1;
	Modify(p[i].y,ly[i]);
	pos[ly[i]].push_back(i);
	m=max(m,ly[i]);
}
for(ll i=0,now;i<(ll)pos[1].size();++i)now=pos[1][i],f[now]=1ll*p[now].x*p[now].y;
for(ll i=2,now;i<=m;++i){
	ST.init(pos[i-1]);
	for(ll j=0;j<(ll)pos[i].size();++j){
		now=pos[i][j];
		f[now]=INF;
		ST.modify(now);
	}
	ST.work();
}
ll ans=INF;
for(ll i=0;i<(ll)pos[m].size();++i){
	ll now=pos[m][i];
	ans=min(ans,f[now]+1ll*(T-p[now].x)*(T-p[now].y));
}

最后放一次完整代码（有修改）

#include<bits/stdc++.h>
#define SIZE_N 300005
#define SIZE_T 1000005
#define INF 2e18
using namespace std;
typedef long long ll;
namespace Mischief{
	struct Node{ll x,y;}p[SIZE_N];
	inline bool cmpx(Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
	ll T,n,m,s,ly[SIZE_N],f[SIZE_N],bit[SIZE_T];
	vector<ll> pos[SIZE_N];
	inline ll LSB(ll x){return x&(-x);}
	inline void Modify(ll x,ll v){for(ll i=x;i<=T;i+=LSB(i))bit[i]=max(bit[i],v);}
	inline ll Query(ll x){ll res=0;for(ll i=x;i;i-=LSB(i))res=max(res,bit[i]);return res;}
	struct Segment_Tree{
		struct Node{
			ll ls,rs;
			vector<ll> trans;
		}a[SIZE_N<<1];
		ll n,size,rt;
		vector<ll> poll,tmp;
		inline void buildSt(ll &rt,ll l,ll r){
			rt=++size;
			a[rt].ls=a[rt].rs=0;
			a[rt].trans.clear();
			if(l==r)return;
			ll mid=(l+r)>>1;
			buildSt(a[rt].ls,l,mid);
			buildSt(a[rt].rs,mid+1,r);
		}
		inline void init(vector<ll> tmp){
			poll=tmp;
			n=tmp.size();
			rt=size=0;
			buildSt(rt,0,n-1);
		}
		inline void Modify(ll rt,ll l,ll r,ll x){
			if(p[x].x>=p[poll[r]].x&&p[x].y>=p[poll[l]].y){
				a[rt].trans.push_back(x);
				return;
			}
			if(p[x].x<=p[poll[l]].x||p[x].y<=p[poll[r]].y)return;
			ll mid=(l+r)>>1;
			Modify(a[rt].ls,l,mid,x);
			Modify(a[rt].rs,mid+1,r,x);
		}
		inline void modify(ll x){Modify(rt,0,n-1,x);}
		inline void Solve(ll l,ll r,ll ql,ll qr){
			ll ans=INF,from=0;
			ll mid=(l+r)>>1,now=tmp[mid];
			for(ll i=ql;i<=qr;++i){
				ll pos=poll[i];
				ll res=f[pos]+1ll*(p[now].x-p[pos].x)*(p[now].y-p[pos].y);
				if(res<ans)ans=res,from=i;
			}
			f[now]=min(f[now],ans);
			if(l<mid)Solve(l,mid-1,from,qr);
			if(mid<r)Solve(mid+1,r,ql,from);
		}
		inline void Work(ll rt,ll l,ll r){
			if(a[rt].trans.size())tmp=a[rt].trans,Solve(0,tmp.size()-1,l,r);
			if(l==r)return;
			ll mid=(l+r)>>1;
			Work(a[rt].ls,l,mid);
			Work(a[rt].rs,mid+1,r);
		}
		inline void work(){Work(rt,0,n-1);}
	}ST;
	inline int _main(){
		scanf("%lld%lld",&n,&T);
		for(ll i=1;i<=n;++i)scanf("%lld%lld",&p[i].x,&p[i].y);
		sort(p+1,p+n+1,cmpx);
		for(ll i=1;i<=n;++i){
			ly[i]=Query(p[i].y)+1;
			Modify(p[i].y,ly[i]);
			pos[ly[i]].push_back(i);
			m=max(m,ly[i]);
		}
		for(ll i=0,now;i<(ll)pos[1].size();++i)now=pos[1][i],f[now]=1ll*p[now].x*p[now].y;
		for(ll i=2,now;i<=m;++i){
			ST.init(pos[i-1]);
			for(ll j=0;j<(ll)pos[i].size();++j){
				now=pos[i][j];
				f[now]=INF;
				ST.modify(now);
			}
			ST.work();
		}
		ll ans=INF;
		for(ll i=0;i<(ll)pos[m].size();++i){
			ll now=pos[m][i];
			ans=min(ans,f[now]+1ll*(T-p[now].x)*(T-p[now].y));
		}
	}
}using namespace Mischief;
int main(){
	_main();
	return 0;
}

什么你不想翻上去点赞？那就点这里吧！