luogu P1725 琪露诺

二次联通门 : luogu P1725 琪露诺

/*

    luogu P1725 琪露诺

    DP + 线段树

    用线段树维护dp[i - R] ~ dp[i - L]的最大值

    然后 转移方程是

        dp[i] = max (dp[i - R], dp[i - R + 1], .... dp[i - L - 1], dp[i - L]) + number[i]

*/

#include <cstdio>

#define Max 200009

#define INF 1e7

inline int max (int a, int b)

{

    return a > b ? a : b;

}

void read (int &now)

{

    now = ;

    bool flag = false;

    register char word = getchar ();

    while (word > '' || word < '')

    {

        if (word == '-')

            flag = true;

        word = getchar ();

    }

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

    if (flag)

        now = -now;

}

int N, L, R;

int number[Max];

struct Segment

{

    struct Segment_Tree

    {

        int l;

        int r;

        int Maxn;

        int Mid;

    };

    Segment_Tree tree[Max << ];

    void Build (int l, int r, int now)

    {

        tree[now].l = l;

        tree[now].r = r;

        if (l == r)

            return ;

        tree[now].Mid = (l + r) >> ;

        Build (l, tree[now].Mid, now << );

        Build (tree[now].Mid + , r, now <<  | );

    }

    int Query_Maxn (int l, int r, int now)

    {

        if (tree[now].l == l && tree[now].r == r)

            return tree[now].Maxn;

        if (r <= tree[now].Mid)

            return Query_Maxn (l, r, now << );

        else if (l > tree[now].Mid)

            return Query_Maxn (l, r, now <<  | );

        else

            return max (Query_Maxn (l, tree[now].Mid, now << ), Query_Maxn (tree[now].Mid + , r, now <<  | ));

    }

    void Change_Single (int pos, int now, int number)

    {

        if (tree[now].l == tree[now].r)

        {

            tree[now].Maxn = number;

            return ;

        }

        if (pos <= tree[now].Mid)

            Change_Single (pos, now << , number);

        else if (pos > tree[now].Mid)

            Change_Single (pos, now <<  | , number);

        tree[now].Maxn = max (tree[now << ].Maxn, tree[now <<  | ].Maxn);

    }

};

Segment Tree;

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

{

    read (N);

    read (L);

    read (R);

    Tree.Build (, N, );

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

    {

        read (number[i]);

        if (i <= L)

            Tree.Change_Single (i, , number[i]);

    }

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

        if (i - L >= L)

            Tree.Change_Single (i, , Tree.Query_Maxn(max(L, i - R), i - L, ) + number[i]);

        else

            Tree.Change_Single (i, , number[i]);

    printf ("%d", Tree.Query_Maxn (N - R, N, ));

    return ;

}