先看贪心版本。
每次种的树在重叠区间越多，种的树越少。只有结束位置才会重合，就对区间结束的位置从小到大排序。
然后遍历每个区间统计第i个区间种了k个树，若k大于 t ，则continue, 否则从区间末尾往前种树。
代码语言：javascript复制//贪心种树
#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("%dn",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
代码语言：javascript复制//差分种树
#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("%dn",dis[n]-mi);
return 0;
} 
