CFR 487 B. Strip ( DP, Monotonic Deque )

題意：
給你 n 個數組成的數列 a，和總和上限 s，長度下限 l。求將數列 a 分割成最少數量的連續片段，滿足每個片段總和不超過 s，長度不小於 l。求最少可能片段數量。

資料規模：
1 ≤ n ≤ 1e5, 0 ≤ s ≤ 1e9, 1 ≤ l ≤ 1e5,- 1e9 ≤ ai ≤ 1e9
TL: 1000 ms
ML: 256 MB

解法：
感覺就很動態規劃，為了加速轉移，需要先預處理 max_reach[ i ] : 以下標 i 當新的片段的左界時，最遠的右界下標，為了方便，是左閉右開 [ i, max_reach[ i ] )。雖然用 RMQ 比較不會錯 ( 而且當時比的人大部份都用 RMQ )，但難得可以用單調性解決：從數列的右邊掃到左邊，同時維護最小值單調雙向佇列和最大值單調雙向佇列。當掃到下標 i 時，在最大值和最小值的差大於 s 的前提下不斷從兩個雙向佇列中把比較後面的下標 pop 出來。最後一個 pop 的下標便是 max_reach[ i ]，但是，如果完全不需要 pop 就是合法的，max_reach[ i ] = max_reach[ i + 1 ]。現在考慮如何動態規劃：
dp[ i ] : 已考慮前 i 個元素，此時最小可能片段數。
dp[ 0 ] = 0,
dp[ i ] = min{ dp[ t ], for all t such that t < i and max_reach[ t ] >= i and t + l >= i } + 1
因為 max_reach 成單調遞增，所以可以對 dp 維護最小值單調雙向佇列。至於 l 的限制，就只是要延遲對應的元素進隊的時間。

時間 / 空間複雜度：
O( N )

int N, S, L;
vi A;

void init(){
  cin >> N >> S >> L;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
}

vi dp;
vi max_reach;

void preprocess(){
  max_reach = vi( N + 1, N );
  deque< int > dqmin, dqmax;
  for( int i = N - 1; i >= 0; --i ){
    while( true ){
      if( dqmin.empty() or A[ dqmin.back() ] < A[ i ] ){
        dqmin.emplace_back( i );
        break;
      }
      dqmin.pop_back();
    }
    while( true ){
      if( dqmax.empty() or A[ dqmax.back() ] > A[ i ] ){
        dqmax.emplace_back( i );
        break;
      }
      dqmax.pop_back();
    }
    max_reach[ i ] = max_reach[ i + 1 ];
    while( true ){
      if( A[ dqmax.front() ] - A[ dqmin.front() ] <= S ){
        break;
      }
      max_reach[ i ] = max( dqmax.front(), dqmin.front() );
      if( dqmax.front() < dqmin.front() ){
        dqmin.pop_front();
      } else if( dqmin.front() < dqmax.front() ){
        dqmax.pop_front();
      } else{
        assert( false );
      }
    }
  }
  dp = vi( N + 1, INF );
  dp[ 0 ] = 0;
  deque< int > dq;
  for( int i = 1; i <= N; ++i ){
    if( i - L >= 0 ){
      while( true ){
        if( dq.empty() or dp[ dq.back() ] < dp[ i - L ] ){
          dq.emplace_back( i - L );
          break;
        }
        dq.pop_back();
      }
    }
    while( not dq.empty() and max_reach[ dq.front() ] < i ){
      dq.pop_front();
    }
    if( not dq.empty() ){
      upmin( dp[ i ], dp[ dq.front() ] + 1 );
    }
  }
}

void solve(){
  if( dp[ N ] == INF ){
    cout << -1 << endl;
  } else{
    cout << dp[ N ] << endl;
  }
}