一本通 1.1 例 2【种树】

贪心即可，先按右端点进行排序，然后对于第$i$个要求，能往右种树就往右种。$O(n*h)$

证明：对于第$i$棵树，如果种它是一种最优情况，那么如果不种$i$，种同样和$i$在$i$第一个出现的建议内$i$的右边没树的地方的树，可以证明这既是合法的，又是可以覆盖到同样多甚至更多的建议的。

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, h, vis[30010], ans;
 5 struct Str {int l, r, num;}stu[5010];
 6 int cmp(Str a, Str b) {return a.r < b.r;}
 7 int main()
 8 {
 9     scanf("%d %d", &n, &h); for(int i = 1; i <= h; ++i) scanf("%d %d %d", &stu[i].l, &stu[i].r, &stu[i].num);
10     sort(stu + 1, stu + h + 1, cmp);
11     for(int i = 1; i <= h; ++i)
12     {
13         int cnt = 0;
14         for(int j = stu[i].l; j <= stu[i].r; ++j) if(vis[j]) ++cnt;
15         if(cnt >= stu[i].num) continue;
16         for(int j = stu[i].r; cnt < stu[i].num; --j) if(!vis[j]) vis[j] = 1, ++cnt;
17     }
18     for(int i = 1; i <= n; ++i) if(vis[i]) ++ans;
19     printf("%d", ans);
20     return 0;
21 }