【hdu3415】Max Sum of Max-K-sub-sequence

2015.03.15 21:53 Sun | 4次阅读 | 旧日oi | 固定链接 | 源码

题意
给一个n个有权值节点的环,求一个长度不超过k的子序列,使点的权值和最小
题解
裸的单调队列
先处理环,把n变成n+k,维护前缀和sum【i】
ans=min(sum[i]-min(sum[j-1]) 1<=i<=n+k,i-k+1<=j<=i)
从1到n+k扫描
先从队尾弹出大于等于当前sum[i-1]的元素
把sum[i-1] 加进队尾
再从队首删掉太远的元素
答案在队首,也就是sum [i]-sum[q.front()]

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define maxn 200005
using namespace std;
int T,n,k;
int num[maxn],sum[maxn];
int ans,st,ed;
deque <int> q;
int main()
{
    cin>>T;
    while(T--)
    {
        q.clear();ans=-0x3f3f3f3f;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        scanf("%d",&num[i]),sum[i]=num[i]+sum[i-1];
        for(int i=n+1;i<=n+k;i++)
        num[i]=num[i-n],sum[i]=sum[i-1]+num[i];
        n+=k;
        for(int i=1;i<=n;i++)
        {
            while(!q.empty()&&sum[q.back()]>sum[i-1]) q.pop_back();
            q.push_back(i-1);
            while(!q.empty()&&q.front()<i-k) q.pop_front();
            if(sum[i]-sum[q.front()]>ans)
            {
                ans=sum[i]-sum[q.front()];
                ed=i;
                st=q.front()+1;
            }
        }
        printf("%d %d %d\n",ans,st,(ed-1)%(n-k)+1);
    }
}
单调队列中保存的是起点,也就是j-1那一项```