# POJ 1180 Batch Scheduling ( Slope Optimization DP )

1180 -- Batch Scheduling

The first line contains the number of jobs N, 1 <= N <= 10000. The second line contains the batch setup time S which is an integer, 0 <= S <= 50. The following N lines contain information about the jobs 1, 2,..., N in that order as follows. First on each of these lines is an integer Ti, 1 <= Ti <= 100, the processing time of the job. Following that, there is an integer Fi, 1 <= Fi <= 100, the cost factor of the job.
TL: 1000 ms
ML: 10000 KB

dp[ i ]：已完成 i 個工作時的最小總花費，加上此 i 個工作的時間對將來的所有工作造成的貢獻。
ts[ i ]：Sigma{ T[ j ] | 0 ≤ j < i }
ps[ i ]：Sigma{ F[ j ] | 0 ≤ j < i }
dp[ i ] = min{ dp[ j ] + ( ts[ i ] - ts[ j ] + S ) * ( ps[ n ] - ps[ j ] ) | 0 ≤ j < i }

O( N )

```const int MAXN = ( int ) 1e4;

int N;
int S;
int T[ MAXN ], F[ MAXN ];

void init(){
cin >> N;
cin >> S;
for( int i = 0; i < N; ++i ){
cin >> T[ i ] >> F[ i ];
}
}

struct line{
int slo, ins;
line( int a, int b ){
slo = a;
ins = b;
}
int operator() ( int x ){
return slo * x + ins;
}
};

int ts[ MAXN + 1 ];
int ps[ MAXN + 1 ];
int dp[ MAXN + 1 ];

int maintain( line a, line b, line c ){
double xab = ( 1.0 * b.ins - a.ins ) / ( 1.0 * a.slo - b.slo );
double yab = xab * a.slo + a.ins;
double yc = xab * c.slo + c.ins;
return yc <= yab;
}

void solve(){
for( int i = 0; i < N; ++i ){
ts[ i + 1 ] = ts[ i ] + T[ i ];
ps[ i + 1 ] = ps[ i ] + F[ i ];
}
deque< line > dq;
for( int i = 0; i < N; ++i ){
line nl = line( - ps[ i ], dp[ i ] + ts[ i ] * ps[ i ] - S * ps[ i ] - ts[ i ] * ps[ N ] );
while( dq.size() >= 2 and maintain( dq[ dq.size() - 2 ], dq.back(), nl ) ){
dq.pop_back();
}
dq.push_back( nl );
while( dq.size() >= 2 and dq[ 0 ]( ts[ i + 1 ] ) >= dq[ 1 ]( ts[ i + 1 ] ) ){
dq.pop_front();
}
dp[ i + 1 ] = dq.front()( ts[ i + 1 ] ) + ( ts[ i + 1 ] + S ) * ps[ N ];
}
cout << dp[ N ] << endl;
}
```