# CFR 19 B. Checkout Assistant ( DP )

Problem - 19B - Codeforces

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

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