DFS+小优化

#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
	int l,r,t;
}a[10100];
bool cmp(Node a,Node b){
	return a.l<b.l;
}
int ans,n,maxn,m,t[10010];
void dfs(int x,int sum,int k){
	if(sum<t[x])t[x]=sum;
	else return ;
	if(x==n || k>=m){
        // if(sum==5)
        //     cout<<x<<" "<<k<<endl;
        // cout<<sum<<endl;
        //cout<<"------"<<endl;
		ans=max(ans,maxn-sum);
		return ;
	}
	for(int i=x;i<n;i++){
		if(a[i].l>k){
            //cout<<a[i].l<<" "<<a[i].r<<endl;
            
			dfs(i+1,sum+a[i].t,a[i].r);
			//需要一个返回 来规定必须参加的课程
			if(a[i].l!=a[i+1].l)break;
		}
	}
}
int main(){
	cin>>maxn>>n;
	
	for(int i=0;i<n;i++){
		t[i]=maxn;
		cin>>a[i].l>>a[i].t;
		a[i].r=a[i].l+a[i].t-1;
	}
	sort(a,a+n,cmp);
    
    m=a[n-1].l;
	dfs(0,0,0);//遍历所有组合  
	cout<<ans;
	return 0;
}

/*
求空闲时间 不上课的时间
如果可以上课 必须去
错过开课时间 就无法去
14 7
1 3
23 7
24 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 1 2 2 2 2 3 3 3
*/