r639.
P5. 製造線的任務調度
標籤
:
Algorithm Challenge contest
Zaim
通過比率: 2人/ 2人 ( 100%) [非即時]
評分方式：
最近更新 : 2025-12-27 18:10
通過比率: 2人/ 2人 ( 100%) [非即時]
評分方式：
Tolerant
最近更新 : 2025-12-27 18:10
內容
你管理一座複雜的工廠，裡面有 n 個模組任務，彼此有依賴關係（形成有向無環圖 DAG）。每個任務 i 有執行時間 t_i（正整數）與獲利 p_i。你可以選擇執行任務但必須遵守依賴（若執行某任務，則其所有前置任務必須先執行）。在總時間 T 內，找出能達到的最大總獲利。要求找出最優值。
給 DAG 上 n 節點、m 有向邊，節點 i 有時間 t_i 與價值 p_i。如果想執行某節點，必須執行其所有前置節點（直接或間接）。在總時間上限 T 內，選取一組節點（須是閉包：對每選擇節點，包含其所有前驅）使得總時間 ≤ T，並使總價值最大。輸出最大價值。
輸入說明
n m T
t1 t2 ... tn
p1 p2 ... pn
接下來 m 行： u v (表示 u -> v，v 依賴 u)
-
1 ≤ n ≤ 2000 -
0 ≤ m ≤ 2000 -
1 ≤ ti ≤ 1000 -
0 ≤ pi ≤ 10^9 -
1 ≤ T ≤ 10^6
輸出說明
單一行：最大總價值
範例輸入
#1
4 3 5 2 2 1 3 3 2 2 4 1 2 1 3 3 4
範例輸出
#1
7
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (5%): 0.5s , <1M
不公開 測資點#1 (5%): 0.5s , <1M
不公開 測資點#2 (5%): 0.5s , <1M
不公開 測資點#3 (5%): 0.5s , <1M
不公開 測資點#4 (5%): 0.5s , <1M
不公開 測資點#5 (5%): 0.5s , <1M
不公開 測資點#6 (5%): 0.5s , <1M
不公開 測資點#7 (5%): 0.5s , <1M
不公開 測資點#8 (5%): 0.5s , <1M
不公開 測資點#9 (5%): 0.5s , <1M
不公開 測資點#10 (5%): 0.5s , <1M
不公開 測資點#11 (5%): 0.5s , <1M
不公開 測資點#12 (5%): 0.5s , <1M
不公開 測資點#13 (5%): 0.5s , <1M
不公開 測資點#14 (5%): 0.5s , <1M
不公開 測資點#15 (5%): 0.5s , <1M
不公開 測資點#16 (5%): 0.5s , <1M
不公開 測資點#17 (5%): 0.5s , <1M
不公開 測資點#18 (5%): 0.5s , <1M
不公開 測資點#19 (5%): 0.5s , <1M
不公開 測資點#0 (5%): 0.5s , <1M
不公開 測資點#1 (5%): 0.5s , <1M
不公開 測資點#2 (5%): 0.5s , <1M
不公開 測資點#3 (5%): 0.5s , <1M
不公開 測資點#4 (5%): 0.5s , <1M
不公開 測資點#5 (5%): 0.5s , <1M
不公開 測資點#6 (5%): 0.5s , <1M
不公開 測資點#7 (5%): 0.5s , <1M
不公開 測資點#8 (5%): 0.5s , <1M
不公開 測資點#9 (5%): 0.5s , <1M
不公開 測資點#10 (5%): 0.5s , <1M
不公開 測資點#11 (5%): 0.5s , <1M
不公開 測資點#12 (5%): 0.5s , <1M
不公開 測資點#13 (5%): 0.5s , <1M
不公開 測資點#14 (5%): 0.5s , <1M
不公開 測資點#15 (5%): 0.5s , <1M
不公開 測資點#16 (5%): 0.5s , <1M
不公開 測資點#17 (5%): 0.5s , <1M
不公開 測資點#18 (5%): 0.5s , <1M
不公開 測資點#19 (5%): 0.5s , <1M
提示 ：
出處:
[管理者：
chenwei98050
...
(陳維（Z）)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||