CFR 158 E. Phone Talks ( DP )

Problem - E - Codeforces

題意：
有 N 通電話，用 T[ i ], D[ i ]，分別為來電時間和通電時間長度描述。保證來電時間嚴格遞增。當有個電話來電時，可以選擇是否無視，如果不無視，就要接起來，佔用 D[ i ] 單位的時間，除非目前是正在打電話的狀態，那麼將這通打進 queue 裡。一個電話的通電結束後，如果 queue 裡有電話，就要立刻接起來，佔用對應的時間。一共可以無視最多 K 通電話，問 [ 1, 86400 ] 這段時間裡，最長一段連續不被佔用的時間長度是多少。

資料規模：
The first input line contains a pair of integers n, k (0 ≤ k ≤ n ≤ 4000) separated by a space. Following n lines contain the description of calls for today. The description of each call is located on the single line and consists of two space-separated integers ti and di, (1 ≤ ti, di ≤ 86400). All ti are distinct, the calls are given in the order of strict increasing ti.
Scheduled times of calls [ti, ti + di - 1] can arbitrarily intersect.
TL: 3000 ms
ML: 256 MB

解法：
dp[ i ][ j ]：已考慮前 i 通電話，已無視 j 通電話，此時 i - j 通電話結束後的第一個空閑時間。
dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ], max( dp[ i - 1 ][ j ], T[ i - 1 ] ) + D[ i - 1 ] )
對於每一個來電時間 T[ i ] 假設其為最長空閑時間的右界，那麼對應的最佳左界一定是 dp[ i ][ min( i, K ) ]。
別忘記檢查 86400 - dp[ N ][ K ]。

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

int N, K;
vi T, D;

void init(){
  cin >> N >> K;
  if( N == 0 ){
    cout << 86400 << endl;
    exit( 0 );
  }
  T = D = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> T[ i ] >> D[ i ];
  }
}

vvi dp;

void preprocess(){
  dp = vvi( N + 1, vi( K + 1, INF ) );
  dp[ 0 ][ 0 ] = 1;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j <= K; ++j ){
      if( j + 1 <= K ){
        upmin( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] );
      }
      upmin( dp[ i + 1 ][ j ], max( dp[ i ][ j ], T[ i ] ) + D[ i ] );
    }
  }
}

void solve(){
  int ans = 86400 - dp[ N ][ K ] + 1;
  for( int i = 0; i < N; ++i ){
    upmax( ans, T[ i ] - dp[ i ][ min( i, K ) ] );
  }
  cout << ans << endl;
}