阿里笔试4.8号

一道ac一道15%

data = list(map(int,input().split()))
T = data[0]

for _ in range(T):
    [n,m,a,b] = list(map(int,input().split()))
    if b==1:
        print(min(n//a,m))
        continue
    if n<a:
        print(0)
        continue
    elif n==a:
        print(min(b,m))
        continue
    if n*b>=m*a:
        print(m)
    else:
        print(n*b//a)

运气AC，推了一下，某些状态下所有木偶都能干掉，然后排除一些特殊情况

def solution(matrix, k, n):
    directions = [[0,1],[1,0],[0,-1],[-1,0]]
    max_re = [0]
    def dfs(i, j, re):
        for dire in directions:
            for step in range(1,k+1):
                new_i, new_j = i+step*dire[0],j+step*dire[1]
                if 0<=new_i<n and 0<=new_j<n:
                    if matrix[new_i][new_j]>matrix[i][j]:
                        max_re[0] = max(re+matrix[new_i][new_j],max_re[0])
                        dfs(new_i, new_j, re+matrix[new_i][new_j])
                else:
                    break
    dfs(0,0,matrix[0][0])
    return max_re[0]

data = list(map(int,input().split()))
T = data[0]

for _ in range(T):
    [n, k] = list(map(int,input().split()))
    matrix = []
    for i in range(n):
        matrix.append(list(map(int,input().split())))
    print(solution(matrix,k,n))

15%,显示的超时，没有思路了，可能python加递归就是这样。555

def solution(matrix, k, n):
    directions = [[0,1],[1,0],[0,-1],[-1,0]]
    dp = [[-1]*n for _ in range(n)]
    def dfs(i, j):
        flag = 0
        re = matrix[i][j]
        temp_max = matrix[i][j]
        for dire in directions:
            for step in range(1,k+1):
                new_i, new_j = i+step*dire[0],j+step*dire[1]
                if 0<=new_i<n and 0<=new_j<n:
                    if matrix[new_i][new_j]>matrix[i][j]:
                        if dp[new_i][new_j]==-1:
                            temp_ans = re + dfs(new_i, new_j)
                        else:
                            temp_ans = re + dp[new_i][new_j]
                        temp_max = max(temp_max, temp_ans)
                else:
                    break
        dp[i][j] = temp_max
        return temp_max
    dfs(0,0)
    print(dp)
    return dp[0][0]

这个应该就能AC了吧，加上dp存储一些已经确定过的点，idea是别人的