链接:

题意:

Given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].

Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

思路:

单调队列,维护一个上升的前缀和,最大值就是Sum[i]-Sum[j],而取不到位置从前面pop,比当前位置大的值从后面pop.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

const int INF = 1e9;

int a[MAXN*2];

int Sum[MAXN*2];

int n, k;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        memset(Sum, 0, sizeof(Sum));

        cin >> n >> k;

        for (int i = 1; i <= n; i++)

            cin >> a[i], a[i + n] = a[i];

        for (int i = 1; i <= n*2; i++)

            Sum[i] = Sum[i - 1] + a[i];

        deque<pair<int, int> > que;

        int res = Sum[1], l=0, r=1;

        for (int i = 0; i <= 2 * n; i++)

        {

            while (!que.empty() && i-que.front().first > k)

                que.pop_front();

            while (!que.empty() && Sum[i] < que.back().second)

                que.pop_back();

            if (!que.empty() && Sum[i]-que.front().second > res)

            {

                res = Sum[i]-que.front().second;

                l = que.front().first;

                r = i;

//                cout << l << ' ' << r << endl;

            }

            que.push_back(make_pair(i, Sum[i]));

        }

        cout << res << ' ' << ((l+1) > n ? l+1-n:l+1) << ' ' << (r > n?r-n:r) << endl;

    }

    return 0;

}

巴特西

HDU-3415-Max Sum of Max-K-sub-sequence(单调队列,带限制的最大子段和)

链接:

题意:

思路:

代码:

最新文章

热门文章