题目传送门
这道题也可以用贪心来做，这里讲一下差分约束的做法。
看到题中给出了 \(m\) 条限制性的语句就联想到差分约束（差分约束的题还是很显眼的）。
做差分约束的题首先得把题面抽象成很多个不等式，所以我们先来转化一下题意。
首先发现求最小值，那么先确定转化方向：将所有条件转换成大于或大于等于，然后建边跑最长路。
设 \(x_i\) 表示前 \(i\) 块地共种了多少个西瓜。
那么对于每个关系可以理解为 \(sum_b - sum_{a - 1} \ge c\)，就是说 \([a, b]\) 这块地种的西瓜数量要大于等于 \(c\)，那么就从 \(a - 1\) 向 \(b\) 连一条长度为 \(c\) 的有向边。
但是光这样建边你会发现根本做不了一点，因为你根本不知道该从哪里开始跑最长路，而且无法正确求解。
这就是这道题非常有意思的一点，因为除了给出的数据需要建边，还有隐藏的建边关系。
注意：
每处最多只能种一个西瓜。
这其实隐藏了一个关系：\(\forall i \in [1,n],0\le x_i - x_{i - 1} \le 1\)。
拆开来看就是：
\[\begin{cases} x_i - x_{i - 1}\ge 0\\ x_{i - 1} - x_i\ge -1 \end{cases} \]所以，要从 \(i - 1\) 向 \(i\) 连一条长度为 \(0\) 的有向边，
从 \(i\) 向 \(i - 1\) 连一条长度为 \(-1\) 的有向边。
综上，再根据刚刚的建图方式，从 \(0\) 号点跑最长路，答案就是 \(x_n\)。
\(\texttt{Code:}\)
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30010, M = 100010;
int n, m, C;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool vis[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int ans;
void spfa(int s) {
queue<int> q;
q.push(s);
memset(dist, -0x3f, sizeof dist);
dist[s] = 0;
vis[s] = true;
while(q.size()) {
int t = q.front();
q.pop();
vis[t] = false;
for(int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if(dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if(!vis[j]) {
vis[j] = true;
q.push(j);
}
}
}
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
add(i - 1, i, 0);
add(i, i - 1, -1);
}
for(int i = 1, a, b, c; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
add(a - 1, b, c);
}
spfa(0);
printf("%d", dist[n]);
return 0;
}