题目链接
差分约束。
设\(s[i]\)表示前\(i\)个位置有多少个数，那么对于一个限制条件\((L,R,C)\)，显然有
\[s[R]-s[L-1]>=C
\]
于是连一条\(L-1\)到\(R\)边权为\(C\)的边。
但为了保证能从\(0\)走到\(max(b)\)，我们还需从\(1\)到\(n\)，对\(i-1\)和\(i\)连一条权为\(0\)的边，对\(i\)和\(i-1\)连一条权为\(-1\)的边，
这也很好理解，因为
\[s[i]-s[i-1]>=0,s[i-1]-s[i]>=-1
\]
显然成立。
然后从\(0\)到\(max(b)\)跑一遍最长路就好了。注意有正权边，所以不能跑Dijkstra，跑SPFA。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define Close fclose(stdin);fclose(stdout);
const int MAXN = 1010;
int n, a, b, c, r;
struct Edge{
int next, to, dis;
}e[MAXN << 2];
int head[MAXN], num;
inline void Add(int from, int to, int dis){
e[++num] = (Edge){ head[from], to, dis };
head[from] = num;
}
queue <int> q;
int dis[MAXN], vis[MAXN];
int main(){
Open("sequence");
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d%d%d", &a, &b, &c);
r = max(r, b);
Add(a - 1, b, c);
}
for(int i = 1; i <= r; ++i)
Add(i - 1, i, 0), Add(i, i - 1, -1);
memset(dis, 128, sizeof dis); dis[0] = 0;
q.push(0);
while(!q.empty()){
int now = q.front();
q.pop();
vis[now] = 0;
for(int i = head[now]; i; i = e[i].next)
if(dis[e[i].to] < dis[now] + e[i].dis){
dis[e[i].to] = dis[now] + e[i].dis;
if(!vis[e[i].to]) q.push(e[i].to), vis[e[i].to] = 1;
}
}
printf("%d\n", dis[r]);
Close;
return 0;
}