【种树】

题目描述

为了绿化乡村,H 村积极响应号召,开始种树了。
H 村里有 n 幢房屋,这些屋子的排列顺序很有特点,在一条直线上。于是方便起见,我们给它们标上 1~n 。树就种在房子前面的空地上。
同时,村民们向村长提出了 m 个意见,每个意见都是按如下格式:希望第 li 个房子到第 ri 个房子的房前至少有 ci 棵树。
因为每个房屋前的空地面积有限,所以每个房屋前最多只能种 k棵树。
村长希望在满足村民全部要求的同时,种最少的树以节约资金。请你帮助村长。

输入格式

输入文件输入第 1 行,包含两个整数 n,m 。
第 2 行,有 n 个整数 ki
第 2~m+1 行,每行三个整数 li,ri,c

输出格式

输出 1 个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。

样例数据 1

输入

5 3
1 1 1 1 1
1 3 2
2 4 2
4 5 1

输出

3

样例数据 2

输入

4 3
3 2 4 1
1 2 4
2 3 5
2 4 6

输出

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数组记录前缀和。
根据题意我们可以得到3个约束条件:
s[r]-s[l-1]≥c,①
s[i]≥s[i-1],②
s[i]-s[i-1]≤k,③
根据①得s[l-1]-s[r]≤-c,在r和l-1之间连一条权值为-c的边。
根据②得s[i-1]-s[i]≤0,在i和i-1之间连一条权值为0的边。
根据③在i-1和i之间连一条权值为k的边。
50分算法:Bellman-Ford。时间复杂度:O(nm)
70分算法:SPFA。时间复杂度:O(km)
100分算法:观察到最大可能需要连150w条边,因此我们要考虑有些边是否需要连。
我们可以只根据条件①计算,每次更新后O(n)检查是否满足条件②和③,如果不满足就修改,这样只用连50w条边,可以过全部数据。

不过我的代码的边全部是反着建的,所以跑的是求最长路的SPFA。

下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*