首页 > 代码库 > HDU 3415 Max Sum of Max-K-sub-sequence 单调队列题解
HDU 3415 Max Sum of Max-K-sub-sequence 单调队列题解
本题又是一题单调队列题解。
技巧就是须要计算好前n项和Sn = a1 + a2 + ... an
这样方便处理。
记录一条单调队列,其意义是: q(head), q(head+1), ...q(tail)
当中头q(head)代表当前最佳解的起点
这样我们仅仅须要在求某点为结尾的S[i] - S[q(head)就得到当前最佳值。
了解了单调数列,知道当中的记录意义,那么这道题就没有难度了。
我也是了解这些信息之后就自己敲出代码的。
只是有些细节没写好也让我WA了几次。
近期少刷水题,而一直都是每天一个新的算法,也学了不少算法了。
#include <stdio.h> #include <limits.h> const int MAX_N = 100001; int N, K; int arr[MAX_N]; int S[MAX_N<<1]; int qu[MAX_N<<1]; int val, sta, end; void getMaxK() { int tail = 0, head = 0; qu[0] = 0; //记录S数组的下标 int len = N+K; val = INT_MIN; for (int i = 1; i < len; i++) { while (tail >= head && S[i-1] <= S[qu[tail]]) tail--; while (tail >= head && qu[head] < i - K) head++;//不能漏了tail>=head qu[++tail] = i-1;//这句能够放前一句前面,那么就能够不用tail>=head推断了 int sum = S[i] - S[qu[head]]; if (sum > val || sum == val && qu[head]+1==sta && i-qu[head]<end-sta+1) { val = sum; sta = qu[head]+1; end = i; } } } int main() { int T; scanf("%d", &T); S[0] = 0; while (T--) { scanf("%d %d", &N, &K); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); S[i] = arr[i] + S[i-1]; } for (int i = 1; i < K; i++) { S[i+N] = arr[i] + S[i+N-1]; } getMaxK(); if (end > N) end = end % N; printf("%d %d %d\n", val, sta, end); } return 0; }
HDU 3415 Max Sum of Max-K-sub-sequence 单调队列题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。