回『初級題庫』
b030: 隨選視訊
標籤 : 動態規劃
通過比率 : 16人/17人 ( 94% ) [非即時]
評分方式：
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)
]

本題狀況 本題討論 排行

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