HDU 5783 Divide the Sequence——贪心

HDU 5783 Divide the Sequence——贪心

这道题关键要理解题意：每个子串的【所有前缀和】都大于等于0，比如1 1 -2，满足1>=0, 1 + 1>=0, 1 + 1 + -2 >= 0

明白这一点后，就能很自然的想出倒着扫的策略

最后注意用long long

#include using namespace std;typedef long long ll;const int MAXN = 1e6 + 10;int T, N;ll a[MAXN];int main() { while (~scanf("%d", &N)) { for (int i = 1; i <= N; i++) scanf("%I64d", &a[i]); int ans = 0; for (int i = N; i >= 1; i--) { if (a[i] >= 0) ans++; else { a[i - 1] += a[i]; } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。