HDU 3415 Max Sum of Max-K-sub-sequence 单调队列

题目大意：给出一个有N个数字的环状序列，让你求一个长度不超过k的和最大的连续子序列。

环状的处理方法一般都是在序列的后面补多一段序列。用s[i]表示到第i位的序列和，对于终点位置为i的序列而言，其长度不超过k的和最大的连续子序列的起点位置就是满足min{s[j]}(j = i-k+1..i-1)的j。显然很容易构造数据卡朴素O(nk)的算法，求区间[i-k+1,i-1]内最小的s[j]就是RMQ问题，用二叉堆、Sparse Table、线段树之类的算法或数据结构可以做到在O(logk)的时间内完成查询，因此总的时间复杂度可以优化到O(nlogk)，对于这题的数据规模而言时限是可以接受的。

但通过单调队列可以将时间复杂度优化到O(n)。对于终点为i的序列，每次插入队列的是s[i-1]，显然队尾数值大于等于s[i-1]的元素是可以删除的，这样即可保证队列的单调性。而队首的要求则是位置大于等于i-k。这样对于每个终点为i的数列，队首即为最优起点。而每个位置的元素最多只会进出队列一次，因此可以保证时间复杂度是O(n)。

3144367    2010-11-02 00:19:10    Accepted    3415    609MS    1840K    944B    C++    IwfWcf