題目1：（阿里筆試題）

小強最近迷上了一款二維平面闖關游戲，在這款游戲中，會有若干個求依次從高處下降，小強需要操控游戲中的小人左右奔跑，來盡可能接到這些球，

現已知該游戲設定如下：

1.每個球有自己的得分且按照順序依次落地，在球落地時，只要小人到達該位置，就可以獲得相應的分數，
2.在一個球落地或者接到手之后，直到下個球落地之前，小強可以移動最多d個單位距離，
3.小人初始在橫軸坐標為0的點，且只能在地面上奔跑，不能升空，即：小人只能在橫軸上左右運動，

輸入描述：
第一行輸入兩個正整數 n , d ( 1 ≤ n ≤ 20 , 1 ≤ d ≤ 5 ) , n,d(1\leq n\leq 20, 1\leq d\leq 5), n,d(1≤n≤20,1≤d≤5), 代表小球個數以及在兩個小球落地間隔之間時間內小人最多能左右移動的距離，
第二行輸入 n n n個整數， x 1 , x 2 , . . . , x n ( 0 ≤ ∣ x i ∣ ≤ 20 ) x_1,x_2,...,x_n(0\leq |x_i|\leq 20) x1?,x2?,...,xn?(0≤∣xi?∣≤20),分別代表每個小球的落地點，且輸入資料以保證按照了落地順序排序，
第三行輸入 n n n個正整數， s 1 , s 2 , . . . , s n ( 1 ≤ s i ≤ 100 ) s_1,s_2,...,s_n(1\leq s_i\leq 100) s1?,s2?,...,sn?(1≤si?≤100),分別代表每個小球的得分，

輸出描述：
輸出僅一行一個正整數，代表這局游戲小強最多能得多少分，

示例1
輸入：
3 1
-1 1 3
1 1 3
輸出：
3

import sys
def myfun(n,xset,sset):
    if n==0:
        return sset[n]
    res=[]
    for i in range(n):
        if (n-i)*d>=abs(xset[n]-xset[i]):
            res.append(myfun(i,xset,sset)+sset[n])
    return max(res)

n,d = map(int,sys.stdin.readline().strip().split())
xset = list(map(int,sys.stdin.readline().strip().split()))
sset=list(map(int,sys.stdin.readline().strip().split()))
# n,d=4,1
# xset=[-1,1,1,3]
# sset=[4,5,6,8]
xset.insert(0,0)
sset.insert(0,0)
res=[]
for i in range(n+1):
    res.append(myfun(i,xset,sset))
print(max(res))

題目2

小強現在有 n n n個物品，每個物品有兩種屬性 x i x_i xi?和 y i y_i yi?，他想要從中挑出盡可能多的物品滿足以下條件：對于任意兩個物品 i i i和 j j j,滿足 x i < x i x_i<x_i xi?<xi?且 y i < y j y_i<y_j yi?<yj?或者 x i > x i x_i>x_i xi?>xi?且 y i > y j y_i>y_j yi?>yj?.問最多能挑出多少物品，
輸入描述：
第一行輸入一個正整數 T T T，表示有 T T T組資料，
對于每組資料，第一行輸入一個正整數 n n n,表示物品個數，
接下來兩行，每行有 n n n個整數，
第一行表示 n n n個節點的 x x x屬性，
第二行表示 n n n個節點的 y y y屬性，
輸出描述：
輸出 T T T行，每一行對應每組資料的輸出，
示例1
輸入
2
3
1 3 2
0 2 3
4
1 5 4 2
10 32 19 21
輸出
2
3
程式：

import sys
import numpy as np
def myfun(n,val,x,y):
    if n==0:
        return 0
    res=[]
    for k in range(n):
        if y[k]<val:
            res.append(myfun(k,y[k],x,y)+1)
    if res:
        return max(res)
    else:
        return 0
def main(n,x,y):
    ind=np.argsort(x)
    y=y[ind]
    res = []
    for k in range(n):
        res.append(myfun(k, y[k],x,y) + 1)
    return max(res)



N=int(sys.stdin.readline().strip())
for i in range(N):
    n=int(sys.stdin.readline().strip())
    x=np.array(list(map(int,sys.stdin.readline().strip().split(' '))))
    y=np.array(list(map(int,sys.stdin.readline().strip().split(' '))))

    res1=main(n,x,y)
    # res1=0
    res2=main(n,-x,-y)
    print(max(res1,res2))