首页 > 代码库 > HDU3415 Max Sum of Max-K-sub-sequence (DP+单调队列)
HDU3415 Max Sum of Max-K-sub-sequence (DP+单调队列)
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3415
题意:
给定一个长度为n的环,求其中一个长度小于等于k的区间,使其和最大,输出最大和,区间的左右端点
分析:
直接想到暴力 dp[i]= sum[i] - sum[i-k+1+j] (0<=j<=k);
但是很明显暴力会超时,就想到用单点队列来维护,一个sum数组,
使其sum尽量小的在前面.处理的时候要将环展开,sum存的是前缀和。
代码如下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> using namespace std; const int maxn = 100010; int a[maxn*2],sum[maxn*2]; int main() { int t,n,k; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++){ scanf("%d",a+i); sum[i]=sum[i-1]+a[i]; a[i+n]=a[i]; } for(int i=n+1;i<=2*n;i++) sum[i]=sum[i-1]+a[i]; deque<int >Q; int ans = -1000000000,st=0,ed=0; for(int i=1;i<=n+k-1;i++){ while(!Q.empty()&&sum[i-1]<sum[Q.back()])//保持队列的单调性 Q.pop_back(); while(!Q.empty()&&Q.front()<i-k)//超过k的长度则消除队列前面的元素 Q.pop_front(); Q.push_back(i-1); if(sum[i]-sum[Q.front()]>ans){ ans=sum[i]-sum[Q.front()]; st=Q.front()+1; ed=i; } } if(ed>n) ed-=n; printf("%d %d %d\n",ans,st,ed); } return 0; }
HDU3415 Max Sum of Max-K-sub-sequence (DP+单调队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。