P3845 [TJOI2007]球赛

简要题意

\(T\) 组数据，每一组数据给出 \(n\) 个数对 \((a,b)\)。你需要将其分为几组，使得组单调不降。求最小组数。

思路

模拟赛考的题。

先来介绍 Dilworth 定理：

对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。

这个定理似乎可以运用到这道题！

如果这样子，本题就被转换成了求最长下降子序列，可以 \(O(n\log n)\) 求。

最后讲一下如何求最长下降子序列，我们可以钦定 \((a,b)\) 中 \(a>b\)。然后按照 \(a,b\) 双关键字排序后二分优化 DP 求最长下降子序列即可。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

bool flag=0;

const int N = 100005;

struct couple{

	int a,b;

	bool operator<(const couple &x) const {

		bool ret=a==x.a?b<x.b:a<x.a;

		if(flag)return !ret;

		else return ret;

	}

} p[N];

int f[N];

int n,t,tot;

signed main(){

// 	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

// 	freopen("line.in","r",stdin);freopen("line.out","w",stdout);

	cin>>t;

	while(t--){

		cin>>n;

		for(int i=1;i<=n;i++){

			scanf("%lld-%lld",&p[i].a,&p[i].b);

			if(p[i].a>p[i].b)swap(p[i].a,p[i].b);

		}

		sort(p+1,p+n+1);

		f[1]=p[1].b;

		tot=1;

		for(int i=2;i<=n;i++){

			if(f[tot]>p[i].b){

				f[++tot]=p[i].b;

			}

			else{

				f[lower_bound(f+1,f+tot+1,p[i].b,greater<int>())-f]=p[i].b;

			}

		}

		cout<<tot<<'\n';

	}

	return 0;

}

巴特西

P3845 [TJOI2007]球赛

简要题意

思路

代码

最新文章

热门文章