P6040 "ACOI 2020"방과 후 기말고사 미끄러운 학원(단조 대기열 최적화 dp)

제목 연결:https://www.luogu.com.cn/problem/P6040
 
아이디어:
데이터 범위를 고려하지 않으면 dp[i]=min(dp[i-j]+a[i]+k+(i-j-1)*d)(i-x<=j
그래서 j의 범위 내에서 틀림없이 한 위치 t가 i를 업데이트하면 가장 큰 dp[i]를 얻을 수 있을 것이다. a[i]+k는 고정값이기 때문에 동태적으로 구간을 구하면 [i-x, i)
범위 내에서 가장 큰 dp[j]-j*d가 좋으므로 단조로운 대기열 유지보수 구간에서 가장 큰 값으로 복잡도가 O(n)로 변경됩니다.
 
코드:

#include 
using namespace std;
typedef long long ll;
const int N = 1e7+10;
int a[N],n,x,tp,Seed;
ll dp[N] = {0},k,d;
int que[N];
inline int rnd () {
	static const int MOD = 1e9;
	return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}

int main(void)
{
    scanf("%d%lld%lld%d%d",&n,&k,&d,&x,&tp);
    if(tp == 0){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    }
    else{
        scanf("%d",&Seed);
        for(int i=1;i<=n;i++){
            a[i] = rnd();
        }
    }

    dp[1] = a[1];
    int top = 0,rear = 0;
    que[rear++] = 1;
    for(int i=2;i<=n;i++)
    {
        if(que[top]+x= dp[i]-d*i) rear--;
        que[rear++] = i;
    }
    printf("%lld
",dp[n]);
    return 0;
}