CFR 19 B. Checkout Assistant ( DP )

Problem - 19B - Codeforces

題意：
有 N 種商品各一個，若購買第 i 種商品，需要花費 C[ i ] 單位的錢，但是可以得到 T[ i ] 單位的店員不注意的時間，而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。

資料規模：
The first input line contains number n (1 ≤ n ≤ 2000). In each of the following n lines each item is described by a pair of numbers ti, ci (0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 1e9). If ti is 0, Bob won't be able to steal anything, while the checkout assistant is occupied with item i.
TL: 1000 ms
ML: 256 MB

解法：
首先店員不注意的時間是可以累加的，而且一旦超過 N 就沒有意義。
可以累加，而且也許可以「借」，也就是就算現在沒有店員不注意的時間可以用，可以先偷這件，以後得到的時候再補也沒關係。因此可以定義動態規劃：
dp[ i ][ j ] : 已獲得前 i 件商品，結算完畢後有 j 單位的店員不注意的時間 ( 允許負值 )
轉移很顯然，詳見代碼
為了方便，這裡用可以存取負下標的陣列，以及滾動陣列。

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

#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x <= v ) return 0;
  x = v; return 1;
}

const int MAXN = 2000;

int N;
int T[ MAXN ], C[ MAXN ];

long long _dp[ 2 ][ ( MAXN + 1 ) * 2 ];
long long *dp[ 2 ] = { &_dp[ 0 ][ MAXN + 1 ], &_dp[ 1 ][ MAXN + 1 ] };

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> T[ i ] >> C[ i ];
  }
  { // initialize
    for( int j = - MAXN; j <= MAXN; ++j ){
      dp[ 0 ][ j ] = 1LL << 50;
    }
    dp[ 0 ][ 0 ] = 0;
  }
  for( int i = 0; i < N; ++i ){
    { // initialize the other side
      for( int j = - MAXN; j <= MAXN; ++j ){
        dp[ ~i & 1 ][ j ] = 1LL << 50;
      }
    }
    for( int j = - MAXN; j <= MAXN; ++j ){
      upmin( dp[ ~i & 1 ][ j - 1 ], dp[ i & 1 ][ j ] ); // steal
      upmin( dp[ ~i & 1 ][ min( N, j + T[ i ] ) ], dp[ i & 1 ][ j ] + C[ i ] ); // buy
    }
  }
  long long ans = 1LL << 50;
  for( int i = 0; i <= N; ++i ){
    ans = min( ans, dp[ N & 1 ][ i ] );
  }
  cout << ans << endl;
  return 0;
}