「LuoguP1645」序列

题意：有一个整数序列，它的每个数各不相同，我们不知道它的长度是多少(即整数个数)，但我们知道在某些区间中间至少有多少个整数，用区间 $(L _i,R _i,C _i)$ 来描述，表示这个整数序列中至少有 $C _i$ 个数来自区间 $[L _i,R _i]$，给出若干个这样的区间，问这个整数序列的长度最少能为多少？

_{一道其实可以用贪心水过的题。}

正解是差分约束系统。

我们假设第 $i$ 个位置有一个数，那么 $a _i=1$，设 $sum _i$ 为 $a _i$ 的前缀和，那么显然满足以下条件：

$$sum _i -sum _{i-1} \ge 0 ;\\ sum _i \le sum _{i-1}+1 ;\\ sum _{R _i}-sum _{L _i -1} \ge C _i;$$

于是转化一下，从 $i-1$ 往 $i$ 连一条边权为 $0$ 的边，从 $i$ 往 $i-1$ 连一条边权为 $-1$ 的边，从 $L _{i} -1$ 往 $R _i$ 连一条边权为 $C _i$ 的边，从 $0$ 到 $\max (R _i)$ 跑一遍最长路就行了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=50101,maxm=1001010;
int n,maxx;
int head[maxn],cnt;
int dis[maxn],ex[maxn];
struct node
{
	int next;
	int to;
	int num;
}e[maxm<<1];
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void spfa()
{
	queue<int> q;
	memset(dis,-0x3f,sizeof(dis));
	memset(ex,0,sizeof(ex));
	dis[0]=0;
	ex[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		ex[u]=0;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[v]<dis[u]+e[i].num)
			{
				dis[v]=dis[u]+e[i].num;
				if(!ex[v])
				{
					ex[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a-1,b,c);
		maxx=max(b,maxx);
	}
	for(int i=0;i<maxx;i++)
	{
		add(i,i+1,0);
		add(i+1,i,-1);
	}
	spfa();
	printf("%d",dis[maxx]);
	return 0;
}