DP/单调队列优化
呃……环形链求最大k子段和。
首先拆环为链求前缀和……
然后单调队列吧<_<，裸题没啥好说的……
WA：为毛手写队列就会挂，必须用STL的deque？（写挂自己弱……sigh）
//HDOJ 3415
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
typedef long long LL;
const int N=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/ int a[N],f[N],q[N+N],s[N];
deque<int>Q;
void work(){
int n=getint(),k=getint();
s[]=;
F(i,,n){
a[i]=getint();
s[i]=s[i-]+a[i];
}
F(i,n+,n+k-) s[i]=s[i-]+a[i-n];
int m=n+k-; int _sum=-INF,pos=,end=;
Q.clear();
F(i,,m){
while(!Q.empty() && s[Q.back()]>s[i-]) Q.pop_back();
while(!Q.empty() && Q.front()<(i-k)) Q.pop_front();
Q.push_back(i-);
if (s[i]-s[Q.front()]>_sum){
_sum=s[i]-s[Q.front()];
pos=Q.front()+;
end=i;
}
}
printf("%d %d %d\n",_sum,pos,(end>n) ? (end-n) : end);
}
int main(){
int T=getint();
while(T--) work();
return ;
}