鏈接: 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; }
版權聲明:本文博客原創文章,博客,未經同意,不得轉載。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
