首页 > 代码库 > hdu 3415 Max Sum of Max-K-sub-sequence(单调队列)

hdu 3415 Max Sum of Max-K-sub-sequence(单调队列)

2024-08-26 14:47:37   215人阅读

题目链接：hdu 3415 Max Sum of Max-K-sub-sequence

题意：

给你一串形成环的数，让你找一段长度不大于k的子段使得和最大。

题解：

我们先把头和尾拼起来，令前i个数的和为sum[i]。

然后问题变成了求一个max{sum[i]-sum[j]}(i-k<j<i)

意思就是对于每一个sum[i]，我们只需要找一个满足条件的最小的sum[j]，然后我们就可以用一个单调队列来维护。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 
 5 const int N=1e5+7,inf=1<<30;
 6 
 7 int t,n,k,sum[2*N],a[N],Q[2*N],ans,l,r;
 8 
 9 void up(int i,int j){if(sum[i]-sum[j]>ans)ans=sum[i]-sum[j],l=j+1,r=i;}
10 
11 int main()
12 {
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d%d",&n,&k);
17         F(i,1,n)scanf("%d",a+i);
18         F(i,1,n)sum[i]=sum[i-1]+a[i];
19         F(i,n+1,2*n)sum[i]=sum[i-1]+a[i-n];
20         int head=1,tail=0;
21         Q[++tail]=0,ans=-inf;//初始化
22         F(i,1,2*n)
23         {
24             while(head<=tail&&(i-Q[head])>k)head++;
25             up(i,Q[head]);
26             while(head<=tail&&sum[Q[tail]]>=sum[i])tail--;
27             Q[++tail]=i;
28         }
29         r%=n;
30         printf("%d %d %d\n",ans,l,r==0?n:r);
31     }
32     return 0;
33 }
View Code

 

hdu 3415 Max Sum of Max-K-sub-sequence(单调队列)


联系
我们