[HDOJ5783]Divide the Sequence（贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5783

题意：给n个数，要求划分成多个段，使得每一个段的任意前缀和都不小于0。

从后往前截取，这样不会影响到未截取的部分。维护当前的前缀和，每次截取不要忘记给前缀和置零。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 1001000;
 6 int n, ret;
 7 LL cur;
 8 LL a[maxn];
 9 
10 int main() {
11     // freopen("in", "r", stdin);
12     while(~scanf("%d", &n)) {
13         ret = 0;
14         for(int i = 1; i <= n; i++) {
15             scanf("%I64d", &a[i]);
16         }
17         int i = n; cur = 0;
18         while(i >= 1) {
19             cur += a[i];
20             if(cur >= 0) {
21                 cur = 0;
22                 ret++;
23             }
24             i--;
25         }
26         printf("%d
", ret);
27     }
28     return 0;
29 }