题目描述
为了绿化乡村，H村积极响应号召，开始种树了。
H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。
同时，村民们向村长提出了m个意见，每个意见都是按如下格式：希望第li个房子到第ri个房子的房前至少有ci棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种ki棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。
输入
输入文件名为tree.in
输入第1行，包含两个整数n，m。
第2行，有n个整数ki。
第2~m+1行，每行三个整数li，ri，ci。
输出
输出文件名为tree.out
输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。
样例输入
tree.in
5 3
1 1 1 1 1
1 3 2
2 4 2
4 5 1
tree.out
3
tree.in
4 3
3 2 4 1
1 2 4
2 3 5
2 4 6
tree.out
8
样例输出
【输入输出样例解释1】 如图是满足样例的其中一种方案，最少要种3棵树。 、
【输入输出样例解释2】 如图是满足样例的其中两种方案，左图的方案需要种9棵树，右图的方案需要种8棵树。可以验证，最少需要种8棵树。
提示
【数据范围】
对于30%的数据，0<n≤100，0<m≤100，ki=1；
对于50%的数据，0<n≤2,000，0<m≤5,000，0<ki≤100；
对于70%的数据，0<n≤50,000，0<m≤100,000，0<ki≤1,000；
对于100%的数据，0<n≤500,000，0<m≤500,000，0<ki≤5,000
这一道题目，我刚开始也想到了差分约束的做法，但是由于我比较脑残。发现现有的约束条件不够（因为我没有意识到s[i] > s[i-1]），所以一直很难想明白这道题目。所以我选择用贪心，简单地说就是把树尽量地往右边种这样子，后边出现的区间就可以在左边少种树，那么少种的树怎么办？我们就把它往右边种，所以说这个贪心策略是可行的。但是这需要数据结构的优化与变形。而且我在打了80多行的时候，膝盖不小心顶到了关机键。。。然后就放弃治疗了。
但是后来经过方科晨的讲解，我就秒懂了，原来我漏了这个东西。
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 int N,M; 10 int num=0; 11 int vet[2000005]; 12 int val[2000005],next1[2000005],head1[2000005]; 13 int flag[2000005],q[2000005],dis[2000005]; 14 15 void add(int u,int v,int cost) 16 { 17 vet[++num]=v; 18 val[num]=cost; 19 next1[num]=head1[u]; 20 head1[u]=num; 21 } 22 23 void SPFA(int s) 24 { 25 for (int i=1; i<=N; i++) 26 { 27 dis[i]=1e9; 28 flag[i]=0; 29 } 30 flag[s]=0; dis[s]=0; 31 int t=0; int w=0; 32 q[0]=s; 33 while (t <= w) 34 { 35 int u=q[t]; 36 t++; 37 for (int e=head1[u]; e!=-1; e=next1[e]) 38 { 39 int cost=val[e]; 40 int V=vet[e]; 41 if (dis[V] > dis[u] + cost) 42 { 43 dis[V]=dis[u] + cost; 44 if (! flag[V]) 45 { 46 flag[V]=1; 47 q[++w]=V; 48 } 49 } 50 } 51 flag[u]=0; 52 } 53 printf("%d\n",abs(dis[N])); 54 } 55 56 int main() 57 { 58 scanf("%d%d",&N,&M); 59 for (int i=0; i<=N; i++) 60 { 61 head1[i]=-1; 62 } 63 for (int i=1; i<=N; i++) 64 { 65 int X; 66 scanf("%d",&X); 67 add(i-1,i,0); 68 add(i,i-1,X); 69 } 70 for (int i=1; i<=M; i++) 71 { 72 int l,r,z; 73 scanf("%d%d%d",&l,&r,&z); 74 add(l-1,r,-z); 75 } 76 SPFA(0); 77 }
