0w1

POJ 1180 Batch Scheduling ( Slope Optimization DP )

1180 -- Batch Scheduling

題意:
有 N 個工作,用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間,以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個,未完成的工作中編號最小的工作,花費其 T 的總和,令之 P,的時間完成。這 k 個工作會同步結束,且其結束時間 Z 為本次操作前的時間值和 P 和輸入時給定的某常數 S 的和,並對總價值造成貢獻各自工作的 F 和 Z 的乘積。求最佳方案下的最小總價值。

資料規模:
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

解法:
第一批工作完成的時間假設為 T1,那麼在這批之後的工作必然會受到 T1 的影響,並且在此階段可以直接求得此 T1 造成的貢獻。因此考慮每次都將對未來的貢獻也一併計入,每次新的一批工作就不需要考慮前一批的結束時間。
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;
}