Problem B:Longest Ordered Subsequence
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
標(biāo)簽：
Subsequence
sequence
Problem
Longest
上傳時(shí)間：
2016-12-08
上傳用戶(hù)：busterman
兩臺(tái)處理機(jī)A 和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器
A 處理時(shí)需要時(shí)間ai，若由機(jī)器B 來(lái)處理，則需要時(shí)間bi。由于各作
業(yè)的特點(diǎn)和機(jī)器的性能關(guān)系，很可能對(duì)于某些i，有ai >=bi，而對(duì)于
某些j，j!=i，有aj<bj。既不能將一個(gè)作業(yè)分開(kāi)由兩臺(tái)機(jī)器處理，也沒(méi)
有一臺(tái)機(jī)器能同時(shí)處理2 個(gè)作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得這兩
臺(tái)機(jī)器處理完成這n 個(gè)作業(yè)的時(shí)間最短（從任何一臺(tái)機(jī)器開(kāi)工到最后
一臺(tái)機(jī)器停工的總時(shí)間）。研究一個(gè)實(shí)例：（a1,a2,a3,a4,a5,a6）=
（2,5,7,10,5,2）；（b1,b2,b3,b4,b5,b6）=（3,8,4,11,3,4）
標(biāo)簽：
處理機(jī)
機(jī)器
上傳時(shí)間：
2014-01-14
上傳用戶(hù)：獨(dú)孤求源
