hdu Max Sum of Max-K-sub-sequence 单调队列优化DP/*求一个环的连续最大子段和。并且输出该最大字段和的和
hdu Max Sum of Max-K-sub-sequence 单调队列优化DP
/*求一个环的连续最大子段和。并且输出该最大字段和的和，启示位置和终止位置。s[i]-s[j]课表示任意最大字段和。当枚举i的时候，只需要求出此时最小的s[j]即可。此时可以维护一个单调上升的队列。每次取队首元素即可为s[j]的最小值。*/#include <stdio.h>#include <cstring>#define maxn 200001struct node{ int num,id; node() {} node(int _num,int _id) { num=_num; id=_id; }} q[maxn];int dp[maxn];int s[maxn];int a[maxn];int main(){ int t,n,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); scanf("%d",&a[1]); s[1]=a[1]; for(int i=2; i<=n; i++) { scanf("%d",&a[i]); s[i]=a[i]+s[i-1]; } for(int i=n+1; i<=n+k; i++) s[i]=a[i-n]+s[i-1]; int max=s[1]; q[0].num=0; q[0].id=1; int l=1,r=1; int head=0,rear=0; for(int i=1; i<=n+k; i++) { while(head<=rear&&q[rear].num>s[i-1]) rear--; q[++rear]=node(s[i-1],i); while(head<=rear&&i+1-q[head].id>k) head++; if(max<s[i]-q[head].num) { max=s[i]-q[head].num; l=q[head].id; r=i; } } if(l>n) l=l-n; if(r>n) r=r-n; printf("%d %d %d\n",max,l,r); } return 0;}