1325 問題 B: [NOIP2006]作業(yè)調(diào)度方案
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 46 解決: 31
題目描述
我們現(xiàn)在要利用m臺(tái)機(jī)器加工n個(gè)工件，每個(gè)工件都有m道工序，每道工序都在不同的指定的機(jī)器上完成。每個(gè)工件的每道工序都有指定的加工時(shí)間。
每個(gè)工件的每個(gè)工序稱為一個(gè)操作，我們用記號(hào)j-k表示一個(gè)操作，其中j為1到n中的某個(gè)數(shù)字，為工件號(hào)；k為1到m中的某個(gè)數(shù)字，為工序號(hào)，例如2-4表示第2個(gè)工件第4道工序的這個(gè)操作。在本題中，我們還給定對(duì)于各操作的一個(gè)安排順序。
例如，當(dāng)n=3，m=2時(shí)，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個(gè)給定的安排順序，即先安排第1個(gè)工件的第1個(gè)工序，再安排第1個(gè)工件的第2個(gè)工序，然后再安排第2個(gè)工件的第1個(gè)工序，等等。
一方面，每個(gè)操作的安排都要滿足以下的兩個(gè)約束條件。
(1) 對(duì)同一個(gè)工件，每道工序必須在它前面的工序完成后才能開始；
(2) 同一時(shí)刻每一臺(tái)機(jī)器至多只能加工一個(gè)工件。
另一方面，在安排后面的操作時(shí)，不能改動(dòng)前面已安排的操作的工作狀態(tài)。
由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號(hào)，仍可得到同樣的安排順序，于是，在輸入數(shù)據(jù)中，我們將這個(gè)安排順序簡寫為“1 1 2 3 3 2”。
還要注意，“安排順序”只要求按照給定的順序安排每個(gè)操作。不一定是各機(jī)器上的實(shí)際操作順序。在具體實(shí)施時(shí)，有可能排在后面的某個(gè)操作比前面的某個(gè)操作先完成。
例如，取n=3,m=2，已知數(shù)據(jù)如下：
工件號(hào) 機(jī)器號(hào)/加工時(shí)間
工序1 工序2
1 1/3 2/2
2 1/2 2/5
3 2/2 1/4
則對(duì)于安排順序“1 1 2 3 3 2”，下圖中的兩個(gè)實(shí)施方案都是正確的。但所需要的總時(shí)間分別是10與12。
當(dāng)一個(gè)操作插入到某臺(tái)機(jī)器的某個(gè)空檔時(shí)（機(jī)器上最后的尚未安排操作的部分也可以看作一個(gè)空檔），可以靠前插入，也可以靠后或居中插入。為了使問題簡單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個(gè)空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的一個(gè)空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。
顯然，在這些約定下，對(duì)于給定的安排順序，符合該安排順序的實(shí)施方案是唯一的，請(qǐng)你計(jì)算出該方案完成全部任務(wù)所需的總時(shí)間。
輸入
輸入第1行為兩個(gè)正整數(shù)，用一個(gè)空格隔開：
m n
（其中m（< 20）表示機(jī)器數(shù)，n（< 20）表示工件數(shù)）
第2行：個(gè)用空格隔開的數(shù)，為給定的安排順序。
接下來的2n行，每行都是用空格隔開的m個(gè)正整數(shù)，每個(gè)數(shù)不超過20。
其中前n行依次表示每個(gè)工件的每個(gè)工序所使用的機(jī)器號(hào)，第1個(gè)數(shù)為第1個(gè)工序的機(jī)器號(hào)，第2個(gè)數(shù)為第2個(gè)工序機(jī)器號(hào)，等等。
后n行依次表示每個(gè)工件的每個(gè)工序的加工時(shí)間。
可以保證，以上各數(shù)據(jù)都是正確的，不必檢驗(yàn)。
輸出
輸出只有一個(gè)正整數(shù)，為最少的加工時(shí)間。
樣例輸入
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情