b276. 4和7
標籤 : DP 动态规划
通過比率 : 32人/68人 ( 47% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-08-11 15:00

內容

萌萌哒doge突然想吃药了!

现在有一排格子,从左向右标号为0到m。doge最初在0号格子中。

一共有n堆药,第i堆药有a[i]粒,被放在b[i]格子里。

每次,萌萌哒doge可以跳到它右边4格或右边7格的位置。求它最多能吃到的药的个数。注意,doge不必跳到格子m,而是可以随时结束游戏。

輸入說明
第一行为两个正整数n,m,分别代表药的堆数与格子坐标的最大值
接下来n行,每行两个正整数a[i],b[i],分别代表某堆药的粒数和位置。
輸出說明

输出一个非负整数,最多能吃到的药的个数。 

範例輸入 #1
3 13
100 4
10 7
1 11
範例輸出 #1
101
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <10M
提示 :

数据范围:

对于20%的数据,n=1,m≤100,000。

对于40%的数据,n≤15,m≤100,000。

对于60%的数据,m≤100,000。

对于100%的数据,n≤100,000,m≤1,000,000,000,a[i]≤10,000,1≤b[i]≤m。

样例解释:

第一次跳4格,第二次跳7格,总共能吃到101粒药。

標籤:
DP 动态规划
出處:
CH #48 [管理者: abs2000 (重回zerojudge立志刷榜...) ]

本題狀況 本題討論 排行

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