Monotonic queue optimization DP

Maximum subsequence sum

Source: https://www.acwing.com/problem/content/137/

Title Description

Enter a length of n n An integer sequence of n, from which a length of no more than m m m, so that the sum of all numbers in the subsequence is the largest.

Note: the length of the subsequence is at least 1 1 1.

Input format

Enter two integers in the first line n , m n,m n,m.

Second line input n n n numbers, representing the length of n n An integer sequence of n.

The number of the same line is separated by a space.

Output format

Output an integer representing the maximum sum of sub orders of the sequence.

Data range

1 ≤ n , m ≤ 300000 1≤n,m≤300000 1≤n,m≤300000

Input sample:

6 4
1 -3 5 1 -2 3

Output example:

7

Train of thought analysis

Optimize DP with sliding window

The problem is to find the maximum sum of subsequences whose length does not exceed m. We know that the sum of a subsequence can be quickly solved by prefix sum, as shown in the figure below

The expression contains two variables, and the double loop time complexity is n 2 n^2 n2, obviously unacceptable.

The common linear method to find the maximum value of interval sum is sliding window, which can fix the left end point or right end point of the interval, and then the other end point can be obtained from the interval through sliding window, and the whole sequence can be traversed by enumerating the fixed end points

Practice 1

We can fix the right endpoint J, because J is on the right side of I, so when enumerating to j, the maximum value of s[i-1] has been calculated, and it is OK to traverse in positive order

Then define some key points of sliding window:

• Section length: no more than m m m, i.e. [i-1, j-1]
• Sliding window boundary: team leader subscript q[hh] < J - M
• Sliding window for minimum value
• Boundary condition: when enumerating to the first element, i-1 is 0, and it should be added to the queue in advance

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 300010;
int a[N];
ll s[N];
ll q[N];
int n, m;
ll res = -2e9;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]), s[i] = s[i-1] + a[i];
    int hh = 0, tt = -1;
    // i represents j in the above analysis
    for (int i = 0; i <= n; i ++)
    {
        if (hh <= tt && q[hh] < i - m) hh ++;
        if (i) res = max(res, s[i] - s[q[hh]]); // Processing boundary, adding s[0] to the queue at the first enumeration
        while(hh <= tt && s[q[tt]] > s[i]) tt --;
        q[++ tt] = i;
    }
    printf("%d\n", res);
    return 0;
}

Practice 2

Fix the left endpoint i, because i is on the right side of J, so when enumerating i-1, we need to use s[j], but s[j] is not found, so reverse enumeration is more appropriate

Then define some key points of sliding window:

• Section length: no more than m m m, i.e. [i-1, j-1]
• Sliding window boundary: leader subscript q[hh] > J
• Sliding window for minimum value
• Boundary condition: in the actual Enumeration, i will start from n-1, but j is not added to the queue at this time, so it needs to start from n, but this step does not calculate the answer, and it can also be carried out during queue initialization

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 300010;
int a[N];
ll s[N];
ll q[N];
int n, m;
ll res = -2e9;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]), s[i] = s[i-1] + a[i];
    int hh = 0, tt = -1;
    // When enumerating, i is used to represent the i - 1 analyzed above
    for (int i = n; i >= 0; i --)
    {
        if (hh <= tt && q[hh] > i + m) hh ++;
        
        if (i < n) res = max(s[q[hh]] - s[i], res);
        while(hh <= tt && s[q[tt]] < s[i]) tt --;
        q[++ tt] = i;
        
    }
    printf("%d\n", res);
    return 0;
}

Travel issues

Source: https://www.acwing.com/problem/content/description/1090/

Title Description

John plans to drive a car around a ring road.

There are altogether n n n stations, each station has several liters of gasoline (some stations may have zero fuel), and each liter of fuel can drive a car for one kilometer.

John must start from a station, walk all the stations clockwise (or counterclockwise) and return to the starting point.

At the beginning, the amount of oil in the car was zero. John took all the oil at each station (the same is true at the starting station). There should be no oil during driving.

Task: judge whether you can successfully travel around a week with each station as the starting point.

Input format

The first line is an integer n n n. Indicates the number of stations on the ring road;

next n n n lines, two integers pi,dipi,di in each line, respectively represent the second i i Fuel storage at station i and No i i Distance from station i to the next station in clockwise direction.

Output format

Output total n n n line, if from No i i Start from station i and drive clockwise (or counterclockwise) all the time. If you can make a successful circle, you will output TAK in line ii, otherwise you will output NIE.

Data range

3 ≤ n ≤ 1 0 6 3≤n≤10^6 3≤n≤106,
0 ≤ p i ≤ 2 × 1 0 9 0≤pi≤2×10^9 0≤pi≤2×109,
0 ≤ d i ≤ 2 × 1 0 9 0≤di≤2×10^9 0≤di≤2×109

Input sample:

5
3 1
1 2
5 2
0 1
5 4

Output example:

TAK
NIE
TAK
NIE
TAK

Train of thought analysis

By analyzing the meaning of the question, it is necessary to replace it with a chain.

Then consider clockwise, from 1 1 Starting from point 1, 1 1 Whether point 1 arrives 2 2 Point 2 is equivalent to oil[1] - dist[1] > = 0, arrival 3 3 Point 3 is equivalent to 1 can reach 2 and oil[1] + oil[2] - (dist[1] + dist[2]). We can find the prefix sum of oil[i]-dist[i] that needs to be counted. Copy oil[i]-dist[i] twice, expand it into a chain, and then sum the prefix. By analogy, walking around point 1 is equivalent to s[1] > = s[0], s[2] > = s[0],..., s[1+n]

Equivalent to min{s[j] - s[k]} > = 0 K = I-1, I,..., j-1

It is basically similar to the previous question, but it is slightly different. For a fixed value, select s[k], that is, enumerate the left endpoint, and use the sliding window to obtain the minimum value of s[j]. At this time, you can choose to enumerate in reverse order.

Why reverse the order?

According to the explanation of the above question, the positive enumeration is traversing because j is on the right i − 1 i-1 When i − 1, you cannot get in the right section j j The minimum value of j, so it needs to traverse in reverse order. But for ontology, it can be in positive or reverse order. But in this problem, the positive order and reverse order are essentially the same, because if you copy it again, the front of the positive order traversal n n n element calculation intervals j j The maximum value of j is followed by the statistical answer

Why enumerate s[i-1]?

Because if you choose to enumerate s[j], s[i-1] needs to calculate the maximum value through the sliding window, but our interval definition is from I to j, that is, the starting point is I, min{s[j] - s[k]} > = 0, k = I-1, I,..., j-1, fixing the left endpoint is meaningless, but for counterclockwise, you need to enumerate like this, and the two are just the opposite

Consider counterclockwise, shilling dist[n] = dist[0], it is OK to find the prefix sum or suffix sum, which is basically the same as the previous question, but it needs to be considered in reverse

Take the second segment as the starting point and extend to the left to get the reverse situation. It is suitable for enumerating the right endpoint. At this time, positive sequence traversal can be adopted

Practice 1:

First pass:

• Section length: no more than m m m, i.e. [i-1, j-1]
• Sliding window boundary: team leader subscript q[hh] < J - M
• Sliding window for minimum value
• Boundary condition: when enumerating to the first element, i-1 is 0, and it should be added to the queue in advance

The second time:

• Section length: no more than m m m, i.e. [i-1, j-1]
• Sliding window boundary: leader subscript q[hh] > J
• Sliding window for minimum value
• Boundary condition: in the actual Enumeration, i will start from n-1, but j is not added to the queue at this time, so it needs to start from n, but this step does not calculate the answer, and it can also be carried out during queue initialization

Clockwise positive traversal:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10, M = 2 * N;
int n;
int w[N], o[N];
ll s[M];
ll q[M];
bool res[N];
int hh, tt;
int read() {
    int t;
    scanf("%d", &t);
    return t;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) w[i] = read(), o[i] = read(), s[i] = s[i+n] = w[i] - o[i];
    for (int i = 1; i <= 2*n; i ++) s[i] += s[i-1];
    
    hh = 0, tt = -1;
    for (int i = 0; i <= 2*n; i ++) // And reverse order are essentially the same
    {
        if (hh <= tt && q[hh] < i - n) hh ++;
        while(hh <= tt && s[q[tt]] > s[i]) tt --;
        q[++ tt] = i;
        if (i > n)
        {
            if (s[q[hh]] >= s[i-n-1]) res[i-n] = 1;
        }
        
    }

    o[0] = o[n];
    for (int i = 1; i <= n; i ++) s[i] = s[i+n] = w[i] - o[i-1];
    for (int i = 1; i <= 2*n; i ++) s[i] += s[i-1];
    
    
    hh = 0, tt = -1;
    for (int i = 0; i <= 2*n; i ++)
    {
        if (hh <= tt && q[hh] < i - n) hh ++;
        if (i > n)
        {
            if (s[i] - s[q[hh]] >= 0) res[i-n] = true;
        }
        while(hh <= tt && s[q[hh]] < s[i]) tt --;
        q[++ tt] = i;
    }
    
    for (int i = 1; i <= n; i ++)
        if (res[i]) puts("TAK");
        else puts("NIE");
    return 0;
}

Clockwise reverse traversal:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10, M = 2 * N;
int n;
int w[N], o[N];
ll s[M];
ll q[M];
bool res[N];
int hh, tt;
int read() {
    int t;
    scanf("%d", &t);
    return t;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) w[i] = read(), o[i] = read(), s[i] = s[i+n] = w[i] - o[i];
    for (int i = 1; i <= 2*n; i ++) s[i] += s[i-1];
    
    hh = 0, tt = -1;
    for (int i = 2*n; i >= 0; i --)
    {
        if (hh <= tt && q[hh] > i + n) hh ++;
        if (i < n)
        {
            if (s[q[hh]] - s[i] >= 0) res[i+1] = true; 
        }
        while(hh <= tt && s[q[tt]] > s[i]) tt --;
        q[++ tt] = i;
    }

    o[0] = o[n];
    for (int i = 1; i <= n; i ++) s[i] = s[i+n] = w[i] - o[i-1];
    for (int i = 1; i <= 2*n; i ++) s[i] += s[i-1];
    
    
    hh = 0, tt = -1;
    for (int i = 0; i <= 2*n; i ++)
    {
        if (hh <= tt && q[hh] < i - n) hh ++;
        if (i > n)
        {
            if (s[i] - s[q[hh]] >= 0) res[i-n] = true;
        }
        while(hh <= tt && s[q[hh]] < s[i]) tt --;
        q[++ tt] = i;
    }
    
    for (int i = 1; i <= n; i ++)
        if (res[i]) puts("TAK");
        else puts("NIE");
    return 0;
}