搜索超时能优化吗
查看原帖
搜索超时能优化吗
828573
CurryNo_1楼主2022/12/29 20:42
#include<iostream>
#include<algorithm>
using namespace std;
long long ans=0,n;
struct match{
	int be;
	int en;
};
match ma[1000010];
bool comp(match x1,match x2)
{
	return x1.be<x2.be;
}
void dfs(long long ti,long long s,long long num)//ti表示为上一场比赛结束的时间,s表示可以参加的比
                                                //赛数量,num表示搜索到第几场比赛 
{
	if(num==n+1)
	{
		ans=max(ans,s);
		return;
	}
	long long tmps=s,tmpnum=num;
	if(ti<=ma[num].be)//有时间可以参加
	{
		dfs(ma[num].en,tmps+1,tmpnum+1);//该场比赛参加 
	}
	dfs(ti,tmps,tmpnum+1);//该场比赛不参加 
	return; 
} 
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
 	{
 		cin >>  ma[i].be >> ma[i].en;
	}
	sort(ma+1,ma+1+n,comp);//通过比赛开始时间排序 
	dfs(0,0,1);
	cout << ans ;
}
2022/12/29 20:42
加载中...