传送门

「Gym102759L」Steel Slicing 2

题目大意

给定一个只有水平边和竖直边的铁片，每次可以水平或竖直方向把一个铁片分成两个部分。注意只能是两个部分。求最少切多少刀才能使得每一个部分都是长方形。

铁片形状如下图，以输入 \(h,l\) 的方式给出。

图挂了

思路

手玩几组数据之后，我们可以发现，一个长方形没有向内凹的角，所以我们需要把向内凹的角全部删除。

为了方便，下面我们将向内凹的角称作凹点，\(h\) 称作上方高度，\(l\) 称作下方高度。

下图中圈出的角都是凹点：

图挂了

可以发现如果我们的切割路径经过了凹点，那么这个凹点就会消失。

因为我们要切割次数尽可能小，所以我们每次的切割经过的凹点要尽可能地多。题目要求只能切成两个部分，所以一次最多消除 \(2\) 个凹点。

考虑先预处理出消除 \(2\) 个凹点的方案。

对于横切，我们可以用一个单调递减栈，每次判断栈顶是否与当前长度相等且不相邻，记录切的位置即可。

然后我们再看竖切。发现只要相邻两个位置的上下长度都不相等，那么就可以消除 \(2\) 个凹点。

我们把能消除 \(2\) 个凹点的竖切方案也记录下来。

然后因为切割路径不能相交，我们不难想到，如果把这些切割路径看作点，相交的路径代表的点之间连边，那么就转化成求最大独立集。

根据某定理，最大独立集 = 点数 - 最大匹配，所以我们只需要求最大匹配。

最大匹配可以在求解竖切时直接贪心。

具体来说，每次把当前位置的横切方案的右端点加入一个小根堆，把与当前位置的竖切方案不相交的弹出。如果这时堆不为空，那么表示有与当前竖切方案相交的横切方案。取堆顶的与当前竖切方案匹配。

因为最大独立集中的边都是能消除 \(2\) 个凸点的，所以最后用凹点个数减去最大独立集就是答案。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
const ll N=1e6+10;
using namespace std;

ll n,m,k;
ll a[N];
ll b[N];
vector<ll>e[N];//边
ll cnt;//总的可以选择的刀数
ll match;//匹配的数量

ll top,s[N];//单调栈
void add(ll a[]){//算横切的方案
	top=1,s[1]=1;//将1入栈
	For(i,2,n){
		while(top&&a[s[top]]>a[i])top--;//大于当前长度就弹出
		if(top&&a[s[top]]==a[i]&&s[top]<=i-2){//等长并且不相邻（相邻不会构成凹点）
			e[s[top--]].pb(i-1);//记录切的位置，这里左闭右开
			cnt++;//统计可选刀数
		}
		s[++top]=i;//入栈
	}
}

priority_queue<ll,vector<ll>,greater<ll>>q;//小根堆

void mian(){
	
	scanf("%lld",&n);
	For(i,1,n){
		scanf("%lld",&a[i]);
		scanf("%lld",&b[i]);
	}
	
	ll ans=0;//凹点总数
	add(a),add(b);//算横切的方案
	For(i,1,n-1){
		for(ll x:e[i])q.push(x);//将相连的点加入堆
		ll res=(a[i]!=a[i+1])+(b[i]!=b[i+1]);//竖切消除的凹点数量
		ans+=res;//统计凹点总数
		if(res==2){//横切消除的数量至少为1，竖切更优只可能是消除两个
			cnt++;//统计可选刀数
			while(q.size()&&q.top()<i)q.pop();//去除不相交的边
			if(q.size()){//有相交的边
				match++;//匹配数+1
				q.pop();
			}
		}
	}
	
	printf("%lld",ans-(cnt-match));//凹点个数-最大独立集
	
}

int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)mian();
	return 0;
}