[HDU3415]Max Sum of Max-K-sub-sequence

题目是求环状序列A的一段长度>=k的子序列，使得子序列的和最大。

因为是的环状的，所以将其长度延长k-1。用sum[i]表示a[1]+…+a[i]，题目转换成求最大sum[i]-sum[j-1]。因为sum[i]是固定的，因此选择最小的sum[j-1]。不妨考虑用单调队列来优化，维护一个单调递增的队列，记下sum[j-1]，每次用队头来更新最大值。 
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

#include <iostream>
using namespace std;

int T, n, k, head, tail, Max, St, Ed, sum[200000], Q[200000], f[200000];
int main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while (T--)
  {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
      cin >> sum[i];
      sum[i+n] = sum[i];
    }
    for (int i = 1; i < n+k; ++i)
      sum[i] += sum[i-1];

    Max = 0x80000000;
    head = 0, tail = -1;
    for (int i = 1; i < n+k; ++i)
    {
      while (head <= tail && Q[head] < i-k) ++head;
      while (head <= tail && sum[i-1]-sum[Q[tail]] <= 0) --tail;
      Q[++tail] = i-1;
      if (sum[i]-sum[Q[head]] > Max)
      {
        Max = sum[i]-sum[Q[head]];
        St = Q[head]+1;
        Ed = (i > n ? i-n : i);
      }
    }
    cout << Max << ' ' << St << ' ' << Ed << endl;
  }
}

Comments