2016多校训练Contest5:1003 Divide the Sequence

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5783

题目翻译

有一个长度为 n 的序列 A1 , A2 , A3 … An .  ( 1n1e6 && 10000A[i]10000 )
求最多能将其分割成多少个子序列,每个序列的每一个前缀都不小于0.

题解

因为是前缀和,所以每一个数只会影响其后面的数,所以我们从后往前做。
对于每一个数,我们暴力的查找它往前延伸多长可以使前缀不小于0,然后贪心做就可以了。
因为每一个数只会被扫到一次,所以复杂度O(N)。

代码