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; }