HDU5783 Divide the Sequence(贪心)

HDU5783 Divide the Sequence(贪心)

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

---

题目

Time Limit:2500MS Memory Limit:65536KB Description Alice has a sequence A, She wants to split A into as much as possible continuous subsequences, satisfying that for each subsequence, every its prefix sum is not small than 0.

Input The input consists of multiple test cases. Each test case begin with an integer n in a single line. The next line contains n integers A1,A2⋯An. 1≤n≤1e6 −10000≤A[i]≤10000 You can assume that there is at least one solution.

Output For each test case, output an integer indicates the maximum number of sequence division.

Sample Input 6 1 2 3 4 5 6 4 1 2 -3 0 5 0 0 0 0 0

Sample Output 6 2 5

---

题意

给你一个数列，求最多有多少个和大于0的连续不相交子序列

---

分析

贪心中经典的子序列问题。直接从后向前处理即可，当前子序列后缀和>=0时开始新序列并重置后缀和。

---

源码

#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<vector> #include<algorithm> #include<string> #include<sstream> #include<cmath> #include<set> #include<map> #include<vector> #include<stack> #include<utility> #include<sstream> #define mem0(x) memset(x,0,sizeof x) #define mem1(x) memset(x,-1,sizeof x) #define dbug cout<<"here"<<endl; //#define LOCAL using namespace std; typedef long long ll; typedef unsigned long long ull; const int INF = 0x3f3f3f3f; const int MAXN = 1e6+10; const int MOD = 1000000007; int a[1001000]; int main(){ #ifdef LOCAL freopen("C:\\Users\\asus-z\\Desktop\\input.txt","r",stdin); freopen("C:\\Users\\asus-z\\Desktop\\output.txt","w",stdout); #endif int n; while(scanf("%d", &n) != EOF){ for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); } int cnt = 0; ll sum = 0; for(int i = n; i >= 1; --i){ sum += a[i]; if(sum >= 0){ cnt++; sum = 0; } } printf("%d\n", cnt); } return 0; }