P1714 cake cutting dp + monotonic queue


Title Description

In fantasy village, qiluno is an ice goblin known as a fool.

One day, qiluno was playing with frozen frogs again, which was to freeze the frogs instantly with ice. But the frog was much smarter than before, and had run to the other side of the river before qiluno came. So cheruno decided to go to the river bank to chase frogs.

The river can be regarded as a row of grids, numbered from 0 to N, and qiluno can only move from the grid with small number to the grid with large number. And qiluno moves in a special way. When she is in grid I, she only moves to any grid in the interval [i+l,i+r]. It's not easy for you to ask why she moves so much, because she's a fool.

Each grid has a freezing index A[i], and the freezing index of the grid numbered 0 is 0. When chiluno stays in that grid, the freezing index A[i] of that grid can be obtained. Chiluno hopes to get the maximum freezing index when she reaches the other side, so that she can teach the frog a lesson.

But because she was so stupid, she decided to ask you to help it decide how to move forward.

At the beginning, qiluno is on the grid with number 0. As long as her next position number is greater than N, she will reach the opposite bank.

Input format

Line 1: 3 positive integers N, L, R

Line 2: N+1 integers. The ith number represents the freezing index A[i-1] of the lattice numbered i-1

Output format

An integer representing the maximum freezing index. Guaranteed not to exceed 2 ^ 31-1

Sample input and output

Enter #1 copy
5 2 3
0 12 3 11 7 -2
Output #1 copy

Description / tips

For 60% of data: n < = 10000

For 100% data: n < = 200000

For all data - 1000 < = a [i] < = 1000 and 1 < = l < = R < = n




Set dp[i] as: the maximum happiness you can get by jumping from point 0 to point I

For dp[i], take a point j in the interval [i-r,i-l], then dp[i]=dp[j]+A[i]

For dp[i+1], take a point j in the interval [i-r+1,i-l+1], then dp[i]=dp[j]+A[i]


Through the above, we can maintain a decreasing queue from head to tail. For an i, we need to judge whether the elements in the head part are in the interval of [i-r,i-l]. If not, we need head++

  5 2 3
    0 12 3 11 7 -2
    Looking at the above examples, we add dp[0] to the queue for the first time to maintain dp[2]
    But then we put dp[1] into the queue to maintain dp[3], but we can't reach position 1 from position 0.
    In practice, we can't use dp[1] to maintain dp[3], but we still put it in the queue.
    But this has no effect on the result, because the dp array is - INF during initialization, so although we put dp[1] into the queue, but
    The value of dp[1] is always very small, which will not affect the following results



using namespace std;
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
#define IO ios::sync_with_stdio(false);cin.tie(0)
int v[maxn],f[maxn],ans,L,R,n;
int que[maxn], head = 1, tail = 1;//Monotone queue, Internal element is location
void Insert(int i)//Insert operation
    for(; f[i] >= f[que[tail]] && tail >= head; ) tail --;//Pop up weights and smaller tail elements
    que[++ tail] = i;//Join the team
int query(int x)
    for(; que[head] + R < x; ) head ++;//The leader of the pop-up team is unreachable x Illegal element of location
    return que[head];//Answer questions
int main()
    for(int i=0;i<=n;++i)
    for(int i = L; i <= n; i ++)
      Insert(i - L); //Transfer the last one to i Join the monotonic queue at
      int from = query(i);//Find the weight and maximum position of the team leader
      //printf("%d %d\n",f[i],v[i]);
      f[i] = f[from] + v[i];//Transfer
      if(i + R > n) ans = max(ans, f[i]);//judge i Can jump to the other side, Calculate the answer
    printf("%d\n", ans);
    return 0;


Posted by James138 on Fri, 13 May 2022 08:47:14 +0300