首页 > 代码库 > HDU 3415 Max Sum of Max-K-sub-sequence 最长K子段和
HDU 3415 Max Sum of Max-K-sub-sequence 最长K子段和
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3415
题意:给出一个数环,要找出其中9长度小于等于K的和最大的子段。
思路:不能采用最暴力的枚举,题目的数据量是10^5,O(N^2)的枚举回去超时,本题采用的很巧妙的DP做法,是用单调队列优化的DP。
运用的是STL的deque,从i:1~a找到以其中以i为尾的符合条件的子段,并将i本身放入双向队列,所有i从队列后放入,保证了队列的单调性。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #include <cmath> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define maxn 100005*2 #define maxm #define INF 0x7fffffff typedef long long ll; using namespace std; int num[maxn],sum[maxn]; int main() { int tot; scanf("%d",&tot); while(tot--) { int a,b; scanf("%d%d",&a,&b); scanf("%d",&num[1]); sum[1]=num[1]; for(int i=2;i<=a;i++) { scanf("%d",&num[i]); sum[i]=sum[i-1]+num[i]; } for(int i=a+1;i<a+b;i++) sum[i]=sum[i-1]+num[i-a]; deque < int > dd; int ans=-INF,head=-1,tail=-1; for(int i=1;i<a+b;i++) { while(!dd.empty()&&sum[i-1]<sum[dd.back()]) dd.pop_back(); while(!dd.empty()&&i>dd.front()+b) dd.pop_front(); dd.push_back(i-1); if(sum[i]-sum[dd.front()]>ans) { ans=sum[i]-sum[dd.front()]; head=dd.front()+1; tail=i; } } if(head>a) head-=a; if(tail>a) tail-=a; printf("%d %d %d\n",ans,head,tail); } return 0; }
HDU 3415 Max Sum of Max-K-sub-sequence 最长K子段和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。