【HDU】5783 Divide the Sequence

本文主要是介绍【HDU】5783 Divide the Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Divide the Sequence

---

题目链接

• Divide the Sequence

---

题目大意

    给定一个序列A，现在要把A分成尽量多的连续子序列，要求每段子序列的每段前缀和都大于0。

---

题解

贪心

    算是这次的签到题把，注意是每段连续子序列的每段前缀和都要大于0（一开始还把这里看错了…），因为每段前缀和都要大于0且一定有解，所以对于每一个负数，它只可能与前面的数成一段，而对于一个正数，如果不需要和后面的数组和的话他一定可以单独作为一段。基于这种思想，我们从后向前贪心，遇到负数就向前配对知道和大于零，对于一个正数，不需要配对的话直接作为一段。
    注意用long long

---

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1000005
#define LL long longusing namespace std;LL n,a[maxn];int main()
{while (scanf("%I64d",&n)!=EOF){for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);LL ans=0,sum=0;for (int i=n;i>0;i--){sum+=a[i];if (sum>=0){ans++;sum=0;}}printf("%I64d\n",ans);}return 0;
}

这篇关于【HDU】5783 Divide the Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---