Intervals

设s[k]表示0~k之间最少选出的个整数。由题意可得：s[bi]-s[ai-1]>=ci;
这很明显是一个差分约束系统的模型。
但是题目中仍有一些隐含条件：
1.s[k]-s[k-1]>=0,很明显。
2.s[k]-s[k-1]<=1.每个数只能选一次，可变形为s[k-1]-s[k]>=-1;
但是只这样做的话，因为a最小为0，所以我们会得到-1这个点，这样不方便，所以可以把0~k都加上一个1.

#include<iostream>
#include<cstdio>
#include<memory.h>
#include<queue>
#include<algorithm>
#include<stack>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
 
using namespace std;
const int maxn=50100;
int read()
{
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		res=res*10+ch-'0';
		ch=getchar();
	}
	return res*f;
}
int n;
int head[maxn],next1[3*maxn],to[3*maxn],dis[maxn],w[3*maxn],cnt;
int vis[maxn],mn;
inline void add(int u,int v,int weight)
{
    cnt++;
	next1[cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	w[cnt]=weight;
}
inline void spfa()
{
	memset(dis,0xc0,sizeof(dis));dis[0]=0;
	queue<int>q;q.push(0);vis[0]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=next1[i])
		{
			int v=to[i];
			int ww=w[i];
			if(dis[v]<dis[u]+ww)
			{
				dis[v]=dis[u]+ww;
				if(!vis[v])
				{
				    q.push(v);
					vis[v]=1;				
				}
			}
		}
	}
}
int main()
{
	n=read();
	rep(i,1,n)
	{
		int u,v,weight;
		u=read();v=read();weight=read();
		add(u,v+1,weight);
        mn=max(mn,v+1);
	}
	rep(i,1,mn)
	{
		add(i-1,i,0);
		add(i,i-1,-1);
	}
	spfa();
	printf("%d\n",dis[mn]);
	return 0;
}