神马品牌网14款英朗gt怎么样:求dp方程式，或更好的方法
来源：百度文库 编辑：神马品牌网 时间：2024/04/29 06:31:44
.题目描述
魔法学校新近流行一种叫Pick Up the Ball（PUB）的单人游戏——一项智力与体力的考验。游戏在一个空旷的场地上举行，N个重量分别为w1、w2……wn的虚拟花环球将分别在时间t1、t2……tn陆续在空中的某处出现并消失。游戏者只能在花环球出现的那一秒(ti秒)以手中的小球框将其接住，否则，就只能放弃这个球了。由于每个小球框只能装载最多MaxWeight重量的球，所以若球i放入框后将超出球框能承受的重量时，球框将自动更新为一个新的空框，并将球i放入新框中。（这种自动游戏系统可是魔法学校的新专利哦！）不过，每个接球手最多只允许换MaxChance次球框，也就是说，当用满MaxChance个框或N个球均已消失后，游戏结束。游戏的得分即为以球框接住的球的个数。魔法学校在游戏开始的前5分钟会将各球出现的时间及地点告诉游戏者，让其作好准备。
“I’ll win! It’s a piece of cake!”哈利·波特拍着胸脯，跃跃欲试。自从魁地奇决赛后，他还一直没有机会碰碰心爱的火弩箭啊。“Oh……”哈利很快发现，要赢得比赛，还要有一个周密的接球方案，即确定他应该接住哪些球才能得到尽可能多的分数。至于体力方面，No Problem！他总能在1秒后到达他的目的地，这是各接球手望尘莫及的——当然，前提是驾驶着火弩箭。现在请你帮助他设计一个接球方案，使他得到最多的分数。
输入格式
输入文件的第一行为一个正整数N（N＜＝1500），第二行是两个数MaxChance和MaxWeight(0<MaxChance<=20,0<MaxWeight<=10000)。以下有N行，每行二个数Ti、Wi，分别表示第i个球的出现时间与重量。(0<=Ti<=10000,0<Wi<=MaxWeight)
输出格式
输出仅一行，为哈利可能得到的最多分数。
样例输入
10
2 50
5 6
0 2
3 9
40 5
1 25
0 23
0 7
2 25
9 4
10 10
样例输出
7
pascal
魔法学校新近流行一种叫Pick Up the Ball（PUB）的单人游戏——一项智力与体力的考验。游戏在一个空旷的场地上举行，N个重量分别为w1、w2……wn的虚拟花环球将分别在时间t1、t2……tn陆续在空中的某处出现并消失。游戏者只能在花环球出现的那一秒(ti秒)以手中的小球框将其接住，否则，就只能放弃这个球了。由于每个小球框只能装载最多MaxWeight重量的球，所以若球i放入框后将超出球框能承受的重量时，球框将自动更新为一个新的空框，并将球i放入新框中。（这种自动游戏系统可是魔法学校的新专利哦！）不过，每个接球手最多只允许换MaxChance次球框，也就是说，当用满MaxChance个框或N个球均已消失后，游戏结束。游戏的得分即为以球框接住的球的个数。魔法学校在游戏开始的前5分钟会将各球出现的时间及地点告诉游戏者，让其作好准备。
“I’ll win! It’s a piece of cake!”哈利·波特拍着胸脯，跃跃欲试。自从魁地奇决赛后，他还一直没有机会碰碰心爱的火弩箭啊。“Oh……”哈利很快发现，要赢得比赛，还要有一个周密的接球方案，即确定他应该接住哪些球才能得到尽可能多的分数。至于体力方面，No Problem！他总能在1秒后到达他的目的地，这是各接球手望尘莫及的——当然，前提是驾驶着火弩箭。现在请你帮助他设计一个接球方案，使他得到最多的分数。
输入格式
输入文件的第一行为一个正整数N（N＜＝1500），第二行是两个数MaxChance和MaxWeight(0<MaxChance<=20,0<MaxWeight<=10000)。以下有N行，每行二个数Ti、Wi，分别表示第i个球的出现时间与重量。(0<=Ti<=10000,0<Wi<=MaxWeight)
输出格式
输出仅一行，为哈利可能得到的最多分数。
样例输入
10
2 50
5 6
0 2
3 9
40 5
1 25
0 23
0 7
2 25
9 4
10 10
样例输出
7
pascal