POJ 1180 Batch Scheduling ( Slope Optimization DP )
題意:
有 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; }