我們現(xiàn)在要利用m臺機器加工n個工件，每個工件都有m道工序，每道工序都在不同的指定的機器上完成。每個工件的每道工序都有指定的加工時間。 
每個工件的每個工序稱為一個操作，我們用記號j-k表示一個操作，其中j為1到n中的某個數(shù)字，為工件號；k為1到m中的某個數(shù)字，為工序號，例如2-4表示第2個工件第4道工序的這個操作。在本題中，我們還給定對于各操作的一個安排順序。 
例如，當(dāng)n=3，m=2時，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個給定的安排順序，即先安排第1個工件的第1個工序，再安排第1個工件的第2個工序，然后再安排第2個工件的第1個工序，等等。 
一方面，每個操作的安排都要滿足以下的兩個約束條件。 
(1) 對同一個工件，每道工序必須在它前面的工序完成后才能開始； 
(2) 同一時刻每一臺機器至多只能加工一個工件。 
另一方面，在安排后面的操作時，不能改動前面已安排的操作的工作狀態(tài)。 
由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號，仍可得到同樣的安排順序，于是，在輸入數(shù)據(jù)中，我們將這個安排順序簡寫為“1 1 2 3 3 2”。 
還要注意，“安排順序”只要求按照給定的順序安排每個操作。不一定是各機器上的實際操作順序。在具體實施時，有可能排在后面的某個操作比前面的某個操作先完成。 
例如，取n=3,m=2，已知數(shù)據(jù)如下： 

則對于安排順序“1 1 2 3 3 2”，下圖中的兩個實施方案都是正確的。但所需要的總時間分別是10與12。 

當(dāng)一個操作插入到某臺機器的某個空檔時（機器上最后的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠后或居中插入。為了使問題 簡單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（1）（2）的條 件下，插入到最前面的一個空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。 
顯然，在這些約定下，對于給定的安排順序，符合該安排順序的實施方案是唯一的，請你計算出該方案完成全部任務(wù)所需的總時間。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點擊這里了解課程詳情

ACM訓(xùn)練