b030: 隨選視訊
標籤 : 動態規劃
通過比率 : 19人/20人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-10 11:14

內容

小綠購買了某線上影視公司提供的隨選視訊方案,只要付一筆費用,就可以觀看總長度 M 分鐘的影片,小綠從該公司提供的影片中挑選了 N 部有興趣的電影,每部電影都有不同的長度以及滿足感,請問你小綠該如何選擇,才能得到最大的滿足感。挑選影片的限制如下:

  1. 影片一定要從頭看到尾,只看一半得不到任何的滿足感。 
  2. 同一部影片只需要看一次,看兩次以上滿足感並不會增加。
  3. 影片的觀賞順序並不會影響它們的滿足感。
輸入說明

第一行有兩個正整數 N、M (1<=N<=100、1<=M<=1000),N 為小綠感興趣的影片數,M 為小綠可以觀賞的影片總長度。接下來有 N 行影片的資料,每行有兩個正整數 L、S (1<=L<=100、1<=S<=500),L 為該影片的長度,S 為該影片的滿足感。

輸出說明

請輸出以 M 為最大總長度時,小綠可以得到的最大滿足感是多少。

範例輸入 #1
4 9
2 3
3 4
4 5
5 6
範例輸出 #1
12
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
提示 :
標籤:
動態規劃
出處:
[管理者:
sagit (sagit)
]


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