Problem solving - extra physical strength (monotone queue optimization DP)

This is a template question. However, the monotonous queue of ssw02 examination room has been written (ssw02 is a real dish).
Tomorrow, there will be the ACM competition system competition for the seniors. Fortunately, tqr06 will form a team.

Problem surface

Now your group is going to take a way. Specifically, this road is divided into N sections, each section has a bulge degree ai.
This tour group has T people, each with a maximum stride of Ki, that is to say, if you are at present, that is to say, if you are at present, that is, if you are at segment x, you can walk to segment x + ki at most next time.
When a person goes downhill, he or she will pass freely when he or she goes downhill. Otherwise, he or she will consume 1 extra physical strength.
Ask everyone the least amount of energy they need.

You can find it in the first K segment every time. After the monotone queue is optimized, the time can pass.
The main points are as follows:
In sorting, the first key is to consume physical energy, maintain monotonic increase, and then maintain monotonic decrease with height as the second key.

AC code 1 (ssw02)

#include<bits/stdc++.h>
using namespace std;
const  int  N =  2000001 ;
inline int read(){
    int s = 0 ;
    char g = getchar() ;
    while(g>'9'||g<'0')g=getchar() ;
    while(g>='0'&&g<='9')s=s*10+g-'0', g = getchar() ;
    return s ;
}  
int  n , T , k , a[ N ] , loc[ N ], q[ N ] , tot = 0   ;
int f[ N ] ;
int main()
{
    freopen("extra.in","r",stdin);
    freopen("extra.out","w",stdout);
    n = read() ;
    for(int i = 1;i <= n ; i++ ) scanf("%d",&a[ i ]);
    T = read() ;
    while( T-- ){
        k = read() ;
        int  head = 1 , tail = 0 ;
        memset( q , 0 , sizeof(q));
        memset( loc, 0 , sizeof(loc));
        memset( f , 0 , sizeof(f) ) ; 
        head = 1 , tail = 0 ; tot = 0 ;f[ 1 ] = 0 ;q[++tail] = 0 ;loc[ tail ] = 1 ;
        for( int i = 2 ; i <= n ; i++ ){
            while( head <= tail && i - loc[ head ] > k ) head++ ; //The team is not empty and the team head is too far away from the team
            ( a[ loc[head] ]>a[ i ] )?f[ i ]=q[head]:f[ i ]=q[head]+1 ;
            while( 1 ){//It's too much trouble to write here
                if( !(head <= tail ) || f[ i ] > q[ tail ] )break ;
                if( f[ i ]==q[ tail ]&&a[ i ]<=a[ loc[ tail ] ])break ; 
                if( head <= tail && a[ i ] > a[ loc[tail] ] && f[ i ] == q[ tail ] )tail--;
                if( head <= tail && f[ i ] < q[ tail ] )tail-- ;
            }//Clear team tail 
            q[ ++tail ] = f[ i ] ; loc[ tail ] = i ; //Bring new elements to the team
        }
        //for( register int i = 1 ; i <= n ; ++i )printf("%d ",f[i] ) ;
        printf("%d\n",f[ n ]) ;
    }
    return 0;
}

Beautiful std

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

using namespace std;

#define dnt long long 
#define inf 0x3f3f3f3f

const int N = 1e6 + 11;

int n, K, f[N], q[N], hd = 1, tl = 0, a[N];

int main() {
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int T; cin>>T;
    while( T -- ) {
        scanf("%d", &K); memset(f, inf, sizeof(f));
        hd = 1, tl = 0;
        f[1] = 0; q[++tl] = 1;
        for(int i = 2; i <= n; i++) {
            while(hd <= tl && q[hd] + K < i) ++ hd;
            f[i] = f[q[hd]] + ((a[q[hd]] <= a[i]) ? 1 : 0);
            while((hd <= tl) && ((f[q[tl]] > f[i]) || ((f[q[tl]] == f[i]) &&( a[q[tl]] < a[i]))))--tl;
            q[++tl] = i;
        }
        printf("%d\n", f[n]);
    }
    return 0;
}

If you have doubts and suggestions, you can leave comments or personal comments. (this question is a board)

If you like my article, please like it. Thank you.