d059: 4.美食外送員
標籤 : 動態規劃
通過比率 : 5人/5人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-11 09:34

內容

最近有一種新興的行業稱為「美食外送員」(以下簡稱外送員),針對網路平台上顧客的訂單,外送員先到店家取餐,再送達下訂的顧客家中,即可得到一筆酬勞。

小裕加入外送員這行業已經有一段時間,由於接單的效率不高,導致收入不如預期。這時他發現其實每天一早就可以知道整天有哪些訂單,只要細心規劃,就可以讓那一天得到更多的酬勞。但是由於訂單的數量太多,小裕不知道該怎麼計算,你能幫他找出那天最高的酬勞有多少嗎? 

輸入說明

輸入資料的第一行有一個正整數T (1<=T<=100),代表下面有T組測試資料。

每組測試資料第一行有一個正整數N (1<=N<=1000),代表這一天有N筆訂單,接下來有N行,每行裡面有三個正整數A、B、C (1<=A<=B<=106、1<=C<=10000),代表這筆訂單是A時間要到店家取餐,B時間送達顧客家,即可得到C的酬勞。在此假設小裕對所有的訂單都有最優先的接單權,而且小裕送達顧客家中,下一個單位時間可瞬間移動至下一個店家門口,而接單過程中,是無法同時再接其他訂單,也就是從A到B時間為該訂單所用,B+1時間起才能再進行下一個訂單。 

輸出說明

針對每組測試資料輸出一行,輸出這一天可獲得的最高酬勞。

範例輸入 #1
1
3
1 4 3
1 2 2
3 4 2
範例輸出 #1
4
範例輸入 #2
1
3
1 4 3
1 2 1
3 4 1
範例輸出 #2
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (40%): 1.0s , <10M
提示 :

評分說明:

本題共有三組測試資料,分數及條件限制如下:

  1. 測資1(得分30%):T=1、N<=10
  2. 測資2(得分30%):T<=10、N<=100
  3. 測資3(得分40%):無限制
標籤:
動態規劃
出處:
中女110 [管理者:
sagit (sagit)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」