先看贪心版本。

每次种的树在重叠区间越多，种的树越少。只有结束位置才会重合，就对区间结束的位置从小到大排序。

然后遍历每个区间统计第i个区间种了k个树，若k大于 t ，则continue, 否则从区间末尾往前种树。 

//贪心种树 
#include <bits/stdc++.h>
using namespace std;
struct N{
	int s,t,e;
	bool operator < (const N b)const {
		return e<b.e;
	}
};
N node[30005];
int book[30005];
int n,m;
int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&node[i].s,&node[i].e,&node[i].t);
	}
	sort(node,node+m);
	int ans=0;
	for(int i =0;i<m;i++){
		int k = 0;
		for(int j = node[i].s;j<=node[i].e;j++)if(book[j])k++;
		if(k>=node[i].t)continue;
		for(int j=node[i].e;j>=node[i].s;j--){
			if(!book[j]){
				book[j]=1;
				k++; ans++;
				if(k>=node[i].t)break;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
 } 

差分约束

题目中有这么几个约束条件

sum[i]是 i 的前缀和。

从u到v: sum[u-1] - sum[v] <= - t

从i-1到i:   sum[i] - sum[i-1] <=1  

从i到i-1:   sum[i-1] - sum[ i ]<=0

最后找一个源点也即N+1,N+1到每个点距离为0   sum[i] - sum[N+1]=0

//差分种树 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define R register
struct N{
	int v,nxt,w;
};
int cnt,n,m;
int S;
N edge[100005];
int head[100005],dis[30005],book[30005];
int read(){
	int x=0,dign=1;
	char c = getchar();
	while(c<'0'||c>'9'){
		if(c=='-')dign=-1;
		c = getchar();
	}
	while(c>='0'&&c<='9'){
		x = x*10 + c - '0';
		c = getchar();
	}
	return x*dign;
}
void add(int u,int v,int w){
	cnt++;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
void spfa(){
	queue<int> q;
	for(R int i=0;i<=n+1;i++)dis[i] = INF;
	dis[S] = 0; book[S] = 1; q.push(S);
	while(!q.empty()){
		int u = q.front(); book[u] = 0; q.pop();
		for(R int v,w,i = head[u];i;i=edge[i].nxt){
			v = edge[i].v; w = dis[u] + edge[i].w;
			if(dis[v]>w){
				dis[v] = w;
				if(!book[v]){
					book[v]=1; q.push(v);
				}
			} 
		}
	}
}
int main()
{
	n = read();
	m = read();
	for(R int i=0;i<m;i++){
		int u,v,w;
		u = read(); v = read(); w = read();
		add(v,u-1,-w);
	}
	for(R int i=1;i<=n;i++){
		add(i,i-1,0);
		add(i-1,i,1);
	}
	for(R int i=0;i<=n;i++)add(n+1,i,0);
	
	S = n+1;
	
	spfa();
	int mi = INF;
	for(int i=0;i<=n;i++)mi = min(mi,dis[i]);
	printf("%d\n",dis[n]-mi);
	return 0;
 }