cogs 920. [東方S1] 琪露诺

二次联通门 : cogs 920. [東方S1] 琪露诺

/*

    cogs 920. [東方S1] 琪露诺

    dp

    方程为dp[i] = max (dp[i - L], dp[i - L + 1] .... dp[i - R - 1], dp[i - R]);

    要用单调队列优化

    记录路径是只需像最短路问题一样记录前驱

    后递归打印即可

*/

#include <cstring>

#include <cstdio>

void read (int &now)

{

    register char word = getchar ();

    bool temp = false;

    for (now = ; word < '' || word > ''; word = getchar ())

        if (word == '-')

            temp = true;

    for (; word >= '' && word <= ''; now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

//#define Online

#define INF 1e9

int N, L, R, Answer = -INF;

int pos;

#define Max 1000001

int dp[Max];

int Queue[Max];

int Head, Tail;

int value[Max], pre[Max];

void Print_road (int now)

{

    if (pre[now] != -)

        Print_road (pre[now]);

    printf ("%d ", now);

}

int main (int argc, char *argv[])

{

#ifdef Online

    freopen ("iceroad.in", "r", stdin);

    freopen ("iceroad.out", "w", stdout);

#endif

    read (N);

    read (L);

    read (R);

    for (int i = ; i <= N; i ++)

        read (value[i]);

    Tail = ;

    memset (pre, -, sizeof pre);

    for (register int i = L, res; i <= N; i ++)

    {

        if (i - L <= )

            continue;

        res = dp[i - L];

        for (; Head <= Tail && (Queue[Head] + L > i || (Queue[Head] + R < i) || (Queue[Head] > i)); Head ++);

        for (; Head <= Tail && (res > dp[Queue[Tail]]); Tail --);

        Queue[++ Tail] = i - L;

        pre[i] = Queue[Head];

        dp[i] = value[i] + dp[Queue[Head]];

        if (Answer < dp[i])

        {

            Answer = dp[i];

            pos = i;

        }

    }

    printf ("%d\n", Answer);

    Print_road (pos);

    printf ("-1");

    return ;

}