二次联通门 : 

 

 

 

/*    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 
     
      #define Max 200009#define INF 1e7inline int max (int a, int b){    return a > b ? a : b;}void read (int &now){    now = 0;    bool flag = false;    register char word = getchar ();    while (word > '9' || word < '0')    {        if (word == '-')            flag = true;        word = getchar ();    }    while (word >= '0' && word <= '9')    {        now = now * 10 + word - '0';        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 << 3];        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) >> 1;        Build (l, tree[now].Mid, now << 1);        Build (tree[now].Mid + 1, r, now << 1 | 1);    }        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 << 1);        else if (l > tree[now].Mid)            return Query_Maxn (l, r, now << 1 | 1);        else            return max (Query_Maxn (l, tree[now].Mid, now << 1), Query_Maxn (tree[now].Mid + 1, r, now << 1 | 1));    }        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 << 1, number);        else if (pos > tree[now].Mid)            Change_Single (pos, now << 1 | 1, number);        tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn);    }};Segment Tree;int main (int argc, char *argv[]){    read (N);    read (L);    read (R);    Tree.Build (0, N, 1);    for (int i = 0; i <= N; i++)    {        read (number[i]);        if (i <= L)            Tree.Change_Single (i, 1, number[i]);     }    for (int i = L + 1; i <= N; i++)        if (i - L >= L)            Tree.Change_Single (i, 1, Tree.Query_Maxn(max(L, i - R), i - L, 1) + number[i]);        else             Tree.Change_Single (i, 1, number[i]);      printf ("%d", Tree.Query_Maxn (N - R, N, 1));    return 0;}