r627. 2. 列印工廠 - 高中生程式解題系統

Content

你擁有一台印刷機，需要處理 $n$ 個印刷任務。每個印刷任務 $i$ 都有三個相關的參數：

開始時間 (Start Time, $s_i$): 任務 $i$ 可以在 $s_i$ 或之後開始印刷。
截止時間 (Deadline, $d_i$): 任務 $i$ 必須在 $d_i$ 或之前完成印刷。
所需時間 (Processing Time, $t_i$): 任務 $i$ 需要 $t_i$ 秒的連續時間來完成印刷。

印刷機在某一秒完成一個印刷品後，可以在下一秒開始時立即開始列印下一個印刷品。

我們希望排定這 $n$ 個印刷任務的執行順序，使得所有任務都能在其截止時間內完成。然而若是讓印刷機空閒時間不足會減損印刷機的壽命，為了維護印刷機的壽命，我們希望最大化印刷機在能夠執行全部任務的前提下，任兩個任務的間隔時間最大值。

任兩個任務的間隔時間定義為：在完成前一個印刷任務與開始下一個印刷任務之間，印刷機閒置的時間長度。

你的任務是找出一個有效的任務排程順序，使得所有任務都能在截止時間內完成，並且印刷機在整個排程中獲得的總休息時間最大。

Input

第一行包含一個整數 $n$（$2 \le n \le 8$），表示印刷任務的總數量。接下來 $n$ 行，每行包含三個非負整數 $s_i, d_i, t_i$（$0 \le s_i < d_i \le 1000$, $1 \le t_i \le d_i - s_i$），分別表示第 $i$ 個任務的開始時間、截止時間和所需時間。

$30$ 分: $n \le 3$
$70$ 分: 無限制

Output

如果存在一個有效的排程順序，使得所有任務都能在截止時間內完成，則輸出最大可能的總休息時間。保證測試資料一定可以存在一個排程方式完成所有任務。

Sample Input #1

Sample Output #1

Sample Input #2

Sample Output #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1K
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1K
公開測資點#17 (5%): 1.0s , <1K
公開測資點#18 (5%): 1.0s , <1K
公開測資點#19 (5%): 1.0s , <1K

Hint ：

Tags:

APCS

出處:

APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

ID	User	Problem	Subject	Hit	Post Date
54080	ericshen1955 ... (暴力又被TLE)	r627	Python 題解 - Life is short，you need itertools	326	2025-11-18 20:50
54471	tcr980328@gm ... (蔡承融)	r627	不是最佳解，但AC，可以參考看看。	62	2026-01-30 19:46
54605	john1100729@ ... (靖諺)	r627	C++ 詳解	12	2026-02-15 15:05
54101	cubeman94033 ... (請輸入暱稱)	r627	解題報告	220	2025-11-22 02:44
54069	guovinn@gmai ... (郭10)	r627	c++題解（內含程式碼與思路）	404	2025-11-17 11:19