2016多校训练Contest5：1003 Divide the Sequence
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5783
题目翻译
有一个长度为 n 的序列 A1 , A2 , A3 … An . ( 1≤n≤1e6 && −10000≤A[i]≤10000 )
求最多能将其分割成多少个子序列，每个序列的每一个前缀都不小于0.
题解
因为是前缀和，所以每一个数只会影响其后面的数，所以我们从后往前做。
对于每一个数，我们暴力的查找它往前延伸多长可以使前缀不小于0，然后贪心做就可以了。
因为每一个数只会被扫到一次，所以复杂度O(N)。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* Author : WNJXYK Problem : 1003 Blog : http://wnjxyk.cn Date : 2016 */ #include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; const int Maxn=1000000; int n; int num[Maxn+5]; long long sum[Maxn+5]; inline void solve(){ //scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&num[i]); sum[0]=0; for (int i=1;i<=n;i++) sum[i]=sum[i-1]+num[i]; int Ans=0; for (int i=n;i>=1;i--){ int len=0; while(i-len>1 && sum[i]-sum[i-len-1]<0) len++; i=i-len; Ans++; } printf("%d\n",Ans); } int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) solve(); return 0; } |
原文链接：2016多校训练Contest5：1003 Divide the Sequence
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!