HDU 3415 Max Sum of Max-K-sub-sequence
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3415
题目翻译
求一个环上的长度不超过K的最大连续子序列和。多解，则输出开头靠前的，再多解，输出长度短的。
题解
单调队列
首先求前缀和，然后，我们单调队列维护，然后直接转移。
代码
|
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 |
//while(true) RP++; #include<cstdio> #include<queue> using namespace std; const int Maxn=100000; int n,k; long long num[Maxn*2+5]; deque<int> que; inline void solve(int T){ scanf("%d%d",&n,&k); for (int i=1;i<=n;i++){ scanf("%I64d",&num[i]); num[n+i]=num[i]; } for (int i=2;i<=2*n;i++) num[i]+=num[i-1]; long long Ans=num[1]; int start=1,end=1; while(!que.empty()) que.pop_back(); for (int i=1;i<=2*n-1;i++){ while(!que.empty() && i-que.front()+1>k) que.pop_front(); while(!que.empty() && num[que.back()-1]>num[i-1]) que.pop_back(); que.push_back(i); if (!que.empty()){ long long nowSum=num[i]-num[que.front()-1]; int nowStart=que.front(); if (nowSum>Ans){ Ans=nowSum; start=nowStart; end=i; } } } printf("%I64d %d %d\n",Ans,(start-1)%n+1,(end-1)%n+1); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(T); return 0; } |
原文链接：HDU 3415 Max Sum of Max-K-sub-sequence
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!