Luogu1714 切蛋糕

Luogu

单调队列板子题。

很明显\[Ans=\max_{1≤i≤n} \{\sum_{j=1}^i P_i-\min_{0≤k<i} \{\sum_{j=1}^k P_j\} \}\]

单调队列维护即可。

#include <iostream>
#include <cstdio>
#include <queue> 

const int max_n =  + ;
const int inf = 0x7f7f7f7f;

int N, M, Ans = -inf;
int sum[max_n];

std::deque <int> q;

inline int read()
{
    register int x = , v = ;
    register char ch = getchar();
    while(!isdigit(ch)) 
    {
        if(ch == '-') v = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << ) + (x << ) + ch - '0';
        ch = getchar();
    }
    return x * v;
} 

int main()
{
    N = read();
    M = read();
    for(int i = ; i <= N; ++i) sum[i] = sum[i - ] + read();
    for(int i = ; i <= N; ++i)
    {
        while(!q.empty() && sum[q.back()] > sum[i]) q.pop_back();
        q.push_back(i);
        while(!q.empty() && i - q.front() > M) q.pop_front();
        Ans = std::max(Ans, sum[i] - sum[q.front()]); 
    }
    printf("%d\n", Ans);
    return ;
}