CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )

題意：
有 N 隻老鼠，用座標描述。有 M 個洞，用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何，才能使所有老鼠進洞。

制約：
1 ≤ N, M ≤ 5000
abs( X[ i ] ), abs( P[ i ] ) ≤ 1e9
C[ i ] ≤ 5000

解法：
首先對於老鼠和洞都先依據座標排序。
先考慮用容易的動態規劃描述轉移：
dp[ i ][ j ]：已考慮完前 i 個洞且已部署前 j 個老鼠時，最小花費總和。
dp[ i ][ j ] = min{ dp[ i - 1 ][ k ] + cost[ j ] - cost[ k ], for all 0 ≤ j - k ≤ C[ i ] }
其中 cost[ x ] 表示前 x 隻老鼠全部移動到第 i 個洞的花費總和。
可以發現，可以用單調隊列水掉，丟一個 dp[ i ][ k ] 進去的時候附加 cost[ N ] - cost[ k ] 讓元素之間可以公平比較。
維護的是一個對 dp 值單調遞增、對已處理人數單調遞增的隊列，過期是看 j - k 是否超過 C[ i ]。
另外，因為顯然有決策單調性，可以對每層進行基於決策點的分治。

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

// 2D / 1D Divide and Conquer Optimization O( N * M lg N )
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
const int MAXM = 5000;

int N, M;
int X[ MAXN ];
int P[ MAXM ], C[ MAXM ];

long long dp[ MAXM + 1 ][ MAXN + 1 ];
long long cost[ MAXN + 1 ];

void dvcq( int lv, int lb, int rb, int ql, int qr ) {
  if( lb > rb ) return;
  int mid = lb + rb >> 1;
  int opt = mid;
  for( int i = max( ql, mid - C[ lv - 1 ] ); i <= min( qr, mid ); ++i ) {
    if( dp[ lv ][ mid ] > dp[ lv - 1 ][ i ] + cost[ mid ] - cost[ i ] ) {
      dp[ lv ][ mid ] = dp[ lv - 1 ][ i ] + cost[ mid ] - cost[ i ];
      opt = i;
    }
  }
  dvcq( lv, lb, mid - 1, ql, opt );
  dvcq( lv, mid + 1, rb, opt, qr );
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> X[ i ];
  }
  sort( X, X + N );
  for( int i = 0; i < M; ++i ) {
    cin >> P[ i ] >> C[ i ];
  }
  { // dirty way to sort P[] and C[] by P
    vector< int > ord( M );
    vector< int > pvec( M ), cvec( M );
    for( int i = 0; i < M; ++i ) {
      ord[ i ] = i;
      pvec[ i ] = P[ i ];
      cvec[ i ] = C[ i ];
    }
    sort( ord.begin(), ord.end(), [ & ]( int i, int j ) { return P[ i ] < P[ j ]; } );
    for( int i = 0; i < M; ++i ) {
      P[ i ] = pvec[ ord[ i ] ];
      C[ i ] = cvec[ ord[ i ] ];
    }
  }
  memset( dp, 0x3f, sizeof( dp ) );
  dp[ 0 ][ 0 ] = 0;
  for( int i = 1; i <= M; ++i ) {
    for( int j = 0; j < N; ++j ) {
      cost[ j + 1 ] = cost[ j ] + abs( X[ j ] - P[ i - 1 ] );
    }
    dvcq( i, 0, N, 0, N );
  }
  if( dp[ M ][ N ] == 0x3f3f3f3f3f3f3f3fLL ) {
    cout << -1 << endl;
  } else {
    cout << dp[ M ][ N ] << endl;
  }
  return 0;
}

// Deque Optimiation O( N * M )
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
const int MAXM = 5000;

int N, M;
int X[ MAXN ];
int P[ MAXM ], C[ MAXM ];

long long dp[ MAXM + 1 ][ MAXN + 1 ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> X[ i ];
  }
  sort( X, X + N );
  for( int i = 0; i < M; ++i ) {
    cin >> P[ i ] >> C[ i ];
  }
  { // dirty way to sort P[] and C[] by P
    vector< int > ord( M );
    vector< int > pvec( M ), cvec( M );
    for( int i = 0; i < M; ++i ) {
      ord[ i ] = i;
      pvec[ i ] = P[ i ];
      cvec[ i ] = C[ i ];
    }
    sort( ord.begin(), ord.end(), [ & ]( int i, int j ) { return P[ i ] < P[ j ]; } );
    for( int i = 0; i < M; ++i ) {
      P[ i ] = pvec[ ord[ i ] ];
      C[ i ] = cvec[ ord[ i ] ];
    }
  }
  memset( dp, 0x3f, sizeof( dp ) );
  dp[ 0 ][ 0 ] = 0;
  for( int i = 1; i <= M; ++i ) {
    deque< pair< long long, int > > dq;
    vector< long long > cost( N + 1 );
    for( int j = 0; j < N; ++j ) {
      cost[ j + 1 ] = cost[ j ] + abs( X[ j ] - P[ i - 1 ] );
    }
    for( int j = 0; j <= N; ++j ) {
      while( not dq.empty() and dq.back().first >= dp[ i - 1 ][ j ] + cost[ N ] - cost[ j ] ) {
        dq.pop_back();
      }
      dq.emplace_back( dp[ i - 1 ][ j ] + cost[ N ] - cost[ j ], j );
      while( j - dq.front().second > C[ i - 1 ] ) {
        dq.pop_front();
      }
      dp[ i ][ j ] = dq.front().first - ( cost[ N ] - cost[ j ] );
    }
  }
  long long ans = dp[ M ][ N ];
  if( ans == 0x3f3f3f3f3f3f3f3fLL ) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}