python问题--请仔查看内容和例子

Question

python
问题内容
你是水银!你可以在1秒内走K米。要想成为x战警，你还需要有良好的判断力，所以你要接受考验。

在这个测试中，你必须沿着一条一维线跑，试图接住掉下来的球。这条线每米被标记为位置0,1，…，1,000,000,000。每一秒钟，一个标有分数的球就会出现在靠近地面的位置上。如果球离你的距离不超过K米，你可以移动去接它。但如果你决定不这样做，球就会掉到地上，然后立即消失。然而，规则是，除非你真的能接住掉下来的球，否则你不能离开你的位置。所以在任何一秒内，如果你移动时没有接住球，你将被取消资格。

目标是收集尽可能高的总分。
为了帮助你计划测试，x战警学院给了你投球的位置顺序和分数。然后你试着写一个程序来计算你可能的最高分!

输入:
•第一行:用空格分隔的三个整数;N(球的数量，N≤1000)，K(一秒钟内你能走的最大距离)，S(在直线上的起始位置)。
0≤K, S≤1,000,000,000
下面N行表示连续几秒内发生的事件。第一行是第一秒，以此类推。每行包含两个整数;球的位置和得分在各自的秒。

输出
一个数字;最高总分。

例子

Answer 1

详细代码如下，递归实现
思路是在递归的时候，当前球可以选择接或者不接，然后求出最大值

def max_score(dis, score, k, s, n, index):
    if index==n:
        return 0
    add = 0
    p1 = max_score(dis, score, k, s, n, index+1)
    if (s-dis[index])<=k and (s-dis[index])>=-k:
        s = dis[index]
        add = score[index]
    p2 = add + max_score(dis, score, k, s, n, index+1)
    if p1>p2:
        return p1
    else:
        return p2

n,k,s=input().split()
n=int(n)
k=int(k)
s=int(s)

dis=[]
score=[]
for _ in range(n):
    _dis,_score = input().split()
    dis.append(int(_dis))
    score.append(int(_score))

#输出最大得分
print(max_score(dis, score, k, s, n, 0))