N個任務排成一個序列在一臺機器上等待完成（順序不得改變），這N個任務被分成若干批，每批包含相鄰的若干任務。從時刻0開始，這些任務被分批加工，第i個任務單獨完成所需的時間是Ti。在每批任務開始前，機器需要啟動時間S，而完成這批任務所需的時間是各個任務需要時間的總和（同一批任務將在同一時刻完成）。每個任務的費用是它的完成時刻乘以一個費用系數(shù)Fi。請確定一個分組方案，使得總費用最小。 例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分組方案是{1,2}、{3}、{4,5}，則完成時間分別為{5,5,10,14,14}，費用C={15,10,30,42,56}，總費用就是153。

第一行是N(1< =N< =5000)。 第二行是S(0< =S< =50)。 下面N行每行有一對數(shù)，分別為Ti和Fi，均為不大于100的正整數(shù)，表示第i個任務單獨完成所需的時間是Ti及其費用系數(shù)Fi。

一個數(shù)，最小的總費用。

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

名校訓練 動態(tài)規(guī)劃