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

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

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