HDU 3415 Max Sum of Max-K-sub-sequence[단조로운 대기열 최적화 dp]

이 문제는 하계의 최대 자단과 무상하계의 최대 자단과 보십시오
hh대소는 이것을 단순한 단조로운 대열 문제로 분류한다. 왜냐하면 이 상태는 이동할 필요가 없기 때문이다. 사실은 상관없다. 사고방식은 모두 똑같다.
아이디어:
단조로운 대기열은 dp가 i로 끝나는 최대 하위 세그먼트와 d[i]=max{sum[i]-sum[k]|k=[i-K, i-1]}을 최적화한다.d[i]=max(f[k])+sum[i]로 변경합니다.f[k]=-sum[k], k=[i-k, i-1]. k>=0 그리고 제목은 링입니다. 서열을 2*n으로 처리하면 됩니다.
코드:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
inline int Rint() { int x; scanf("%d", &x); return x; }
inline int max(int x, int y) { return (x>y)? x: y; }
inline int min(int x, int y) { return (x<y)? x: y; }
#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(x) for(int i=0; i<(x); i++)
typedef long long int64;
#define INF (1<<30)
const double eps = 1e-8;
#define bug(s) cout<<#s<<"="<<s<<" "

//	      dp
//	 i         d[i] = max{ sum[i]-sum[k] | k=[i-K , i-1] }.
//	  	d[i] = max(f[k])+sum[i]. f[k]=-sum[k], k=[i-k, i-1]. k>=0
//	  ,     ,       2*n   .

#define MAXN 100002*2	// 
int sum[MAXN];

int f[MAXN];
int q[MAXN];
int front, tail;

int main()
{
	int T = Rint();
	while(T--)
	{
		sum[0] = 0;
		int n = Rint();
		int K = Rint();
		FOR(i, 1, n)
		{
			int t = Rint();
			sum[i]=sum[i-1]+t;
			sum[i+n] = sum[i];
		}
		FOR(i, 1+n, n+n)
		{
			sum[i] += sum[n];
		}
		front = tail = 0;
		f[0] = 0;
		int maxd = -INF;
		int st=1, en=1;
		FOR(i, 1, n*2)
		{
			f[i] = -sum[i];
			//	 i-1    
			while(front<tail && f[q[tail-1]]<f[i-1]) tail--;
			q[tail++] = i-1;

			//	 d[i]
			int low = max(i-K, 0);
			while(q[front]<low) front++;
			int d = f[q[front]]+sum[i];
			if(d>maxd)
			{
				maxd = d;
				st = q[front]+1;	//     st ,     n
				en = i>n? i-n: i;
			}
		}
		printf("%d %d %d
", maxd, st, en);
	}
}