懒得复制，戳我戳我

Solution:

• 这道题就是一个板子题
• 抽象成第\(a\)至第\(b\)间选择数的个数为\(c\)，我们就可以用前缀和来表示，这样就可以得到不等式\(s[b]-s[a-1]>=c\)，然后就可以差分约束了
• 这一个约束条件不够，因为每个数只能选择一次，所以补上\(s[i+1]-s[i]>=0\)和\(s[i+1]-s[i]<=1\)，注意存在\(0\)与\(-1\)的连边，我们可以吧\(-1\)拿出来用大于\(50000\)的数字来表示
• 然后求单元最大路径，随后的\(s[50000]\)就是所求解

---

Code:

//It is coded by Ning_Mew on 3.27

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=5e5+10;

int n;

int head[maxn],cnt=-1,dist[maxn];

struct Edge{

  int nxt,to,dis;

}edge[maxn*5];

void add(int from,int to,int dis){

  edge[++cnt].nxt=head[from];

  edge[cnt].to=to;

  edge[cnt].dis=dis;

  head[from]=cnt;

}

void SPFA(){

  queue<int>Q;while(!Q.empty())Q.pop();

  bool vis[maxn]; memset(vis,false,sizeof(vis));

  Q.push(50001);vis[50001]=true;

  while(!Q.empty()){

    int u=Q.front();Q.pop();vis[u]=false;

    for(int i=head[u];i!=-1;i=edge[i].nxt){

      int v=edge[i].to;

      if(dist[v]<dist[u]+edge[i].dis){

    dist[v]=dist[u]+edge[i].dis;

    if(!vis[v]){vis[v]=true;Q.push(v);}

      }

    }

  }

}

int main(){

  scanf("%d",&n);

  memset(head,-1,sizeof(head));

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

    int a,b,c;

    scanf("%d%d%d",&a,&b,&c);

    add(a-1,b,c);

  }

  add(50001,0,0);add(0,50001,-1);

  for(int i=1;i<=50000;i++){add(i-1,i,0);add(i,i-1,-1);}

  memset(dist,-0x5f,sizeof(dist));

  dist[50001]=0;

  SPFA();

  printf("%d\n",dist[50000]);

  return 0;

}