Bangladesh OI 2016 National Round pD. One Punch Man ( DP )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意：
有 N 個怪獸，用 ( X[ i ], V[ i ] )，一維座標及強度描述。有一種操作，先選擇座標，假設為 x，那麼 [ x - R, x + R ] 間的怪獸全部都會被消滅。求操作數不超過 K 的前提下消滅的最大的怪獸強度總值。

資料規模：
T ≤ 10, 1 ≤ N ≤ 1e5
1 ≤ Vi ≤ 1e4
1 ≤ K ≤ 50.
For easy version: 0 ≤ R, Xi ≤ 1e4
For hard version: 0 ≤ R, Xi ≤ 1e8
TL: 1500 ms
ML: 256 MB

解法：
先把輸入整理乾淨，讓座標不重複，並由座標小到大排序。
現在當我們想打倒位於 x[ i ] 的怪獸，但不想打倒 x[ i - 1 ] 的怪獸時，最佳策略顯然是操作魚 x[ i ] + R 的位子。
這麼一來下次要開始考慮的地方也很顯然。
預處理出進行打倒位於 x[ i ] 的怪獸而不打倒 x[ i - 1 ] 的最佳策略操作後，下次開始考慮的位子。
這麼一來轉移時間為 O( 1 )，狀態數為 O( N * K )。
dp[ n ][ k ]：已考慮前 n 個決策點，進行了 k 次操作，此時消滅的最大可能怪獸強度總值。

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

void solve(){
  int T; cin >> T;
  for( int kase = 1; kase <= T; ++kase ){
    cout << "Case " << kase << ": ";
    int N, R, K; cin >> N >> R >> K;
    vp _monster( N );
    for( int i = 0; i < N; ++i ){
      cin >> _monster[ i ].first >> _monster[ i ].second;
    }
    sort( _monster.begin(), _monster.end() );
    vp monster;
    for( int i = 0; i < N; ++i ){
      int j;
      for( j = i + 1; j < N; ++j ){
        if( _monster[ j ].first != _monster[ i ].first ){
          break;
        }
      }
      int sum = 0;
      for( int k = i; k < j; ++k ){
        sum += _monster[ k ].second;
      }
      monster.emplace_back( _monster[ i ].first, sum );
      i = j - 1;
    }
    vi jump2( monster.size() ); // next unsolved pos if hit at here + R
    for( int i = 0; i < monster.size(); ++i ){
      int p = monster[ i ].first + R;
      if( i == 0 ){
        int j;
        for( j = 1; j < monster.size(); ++j ){
          if( monster[ j ].first - p > R ){
            break;
          }
        }
        jump2[ i ] = j;
      } else{
        int j;
        for( j = jump2[ i - 1 ]; j < monster.size(); ++j ){
          if( monster[ j ].first - p > R ){
            break;
          }
        }
        jump2[ i ] = j;
      }
    }
    vi ps( monster.size() + 1 );
    for( int i = 0; i < monster.size(); ++i ){
      ps[ i + 1 ] = ps[ i ] + monster[ i ].second;
    }
    vvi dp( monster.size() + 1, vi( K + 1, -INF ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 0; i < monster.size(); ++i ){
      for( int j = 0; j <= K; ++j ){
        upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] );
        if( j + 1 <= K ){
          upmax( dp[ jump2[ i ] ][ j + 1 ], dp[ i ][ j ] + ps[ jump2[ i ] ] - ps[ i ] );
        }
      }
    }
    int ans = 0;
    for( int i = 0; i <= K; ++i ){
      upmax( ans, dp[ monster.size() ][ i ] );
    }
    cout << ans << endl;
  }
}