首页 > 代码库 > HDU 5783 Divide the Sequence（数列划分）
HDU 5783 Divide the Sequence（数列划分）
HDU 5783 Divide the Sequence（数列划分）
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem 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.
CN
Alice有一个数列A，她想把A拆分出尽可能多的子串，并且每个子串的任意前缀和都大于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.
CN
Output - 输出
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.
多组测试用例。 每组测试用例的第一行为一个整数n。 下一行有n个整数A1,A2?An。 1≤n≤1e6 ?10000≤A[i]≤10000 你可以认为不存在无解的情况。
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
题解
贪心，一开始看错题目了，一直想不出解法，浪费了巨多时间……
某子串1 2 3的所有前缀为
1 1 2 1 2 3
显然如果出现负数的话，需要前面的正数来凑，反正无法满足条件。
做法就是从后往前扫描，记录临时的后n项和，>=0则清空，划分数+1。
极限数据应该是5e5 * 10000 = 5e9，单纯的int会超，需要__int64。
代码 C++
1 #include <cstdio> 2 __int64 data[1000001]; 3 int main(){ 4 __int64 n, i, opt, tmp; 5 while (~scanf("%I64d", &n)){ 6 for (i = opt = tmp = 0; i < n; ++i) scanf("%I64d", data + i); 7 for (--i; ~i; --i){ 8 tmp += data[i]; 9 if (tmp >= 0) tmp = 0, ++opt; 10 } 11 printf("%I64d\n", opt); 12 } 13 return 0; 14 }
HDU 5783 Divide the Sequence（数列划分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。