可以用搜索写吗,之过了四个点
查看原帖
可以用搜索写吗,之过了四个点
504237
lk323232楼主2022/8/31 11:23
#include<bits/stdc++.h>
using namespace std;
int n,vis[10000],dp[10000],ans;
struct a{
	int l,w;
}mu[10000];
int cmp(a &x,a &y){
	if(x.l==y.l) return x.w>=y.w;
	return x.l>=y.l;
}
void dfs(int k){
	vis[k]=1;
	for(int i=k+1;i<=n;++i){
		if(!vis[i]&&mu[i].l<=mu[k].l&&mu[i].w<=mu[k].w)
		dfs(i);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>mu[i].l>>mu[i].w;
	sort(mu+1,mu+n+1,cmp);
	for(int i=1;i<=n;++i){
		if(!vis[i]) dfs(i),ans++;
	}
	cout<<ans;
	return 0;
}
2022/8/31 11:23
加载中...