华为9.21笔试复盘（100，45，10 = 220）

第二题，给定一个地图；上面有'X'和'S'以及'.'，'X'表示障碍物，'S'表示驿站；可以将马变为兵，可以将兵变为马；类型转换需要耗时+1；不转化不耗时。开始在（0，0）处初始位置为兵；希望走到地图右下角；且兵为上下左右每次移动一格；
马按照国际象棋走法有8个方向。求左上到右下的最短时间，如果无法到达返回-1.
解析：当时想着最小，dp啥的；结果不行。实际上深搜就可以解决复杂度为O（MN）.如果搜索的时间大于等于原来这个位置的时间则返回。


mat = [['.','.','.','.','.','.','.','.','.'],
       ['.','.','.','.','.','X','X','X','.'],
       ['.','.','.','.','.','X','.','X','.'],
       ['.','.','.','.','.','X','.','X','.'],
       ['.','.','.','.','.','X','.','X','S'],
       ['X','X','X','X','X','X','.','X','X'],
       ['S','.','.','.','.','.','.','.','.'],
       ['.','.','.','.','.','.','.','.','.'],
       ['.','.','.','.','.','.','.','.','.']
]
m = 9
n = 9
timeBin = [[float('inf')]*n for _ in range(m)]
timeMa = [[float('inf')]*n for _ in range(m)]
def DFSBin(x,y,cost):
    if x<0&nbs***bsp;x>=m&nbs***bsp;y<0&nbs***bsp;y>=n:
        return 
    if mat[x][y]=='X'&nbs***bsp;timeBin[x][y]<=cost:
        return
    
    timeBin[x][y] = cost
    if mat[x][y]=='S':
        DFSMa(x,y,cost+1)
    DFSBin(x-1,y,cost+1)
    DFSBin(x+1,y,cost+1)
    DFSBin(x,y-1,cost+1)
    DFSBin(x,y+1,cost+1)
def DFSMa(x,y,cost):
    if x<0&nbs***bsp;x>=m&nbs***bsp;y<0&nbs***bsp;y>=n:
        return 
    if mat[x][y]=='X'&nbs***bsp;timeMa[x][y]<=cost:
        return    
    
    timeMa[x][y] = cost
    if mat[x][y]=='S':
        DFSBin(x,y,cost+1)
    
    DFSMa(x-2,y-1,cost+1)
    DFSMa(x-1,y-2,cost+1)
    
    DFSMa(x+2,y-1,cost+1)
    DFSMa(x+1,y-2,cost+1)
    
    DFSMa(x-2,y+1,cost+1)
    DFSMa(x-1,y+2,cost+1)
    
    DFSMa(x+2,y+1,cost+1)
    DFSMa(x+1,y+2,cost+1)
DFSBin(0,0,0) 

第三题，一条路上要栽树，给定了po：树的位置，r：树长成后的半径，val树的观赏价值；问得到的最大观赏价值是多少；树长成后不可重叠。

考虑是不是属于区间dp的问题？300分很吓人没有做。

其实就dp考虑每棵树即可。

dp[i][0]不栽i树能获得的最大观赏价值

dp[i][1]栽i树能获得的最大观赏价值

考察i以及之前的树，不考虑后续的树；典型的dp问题

状态转移方程：

dp[i][0] = max(dp[i-1][1],dp[i-1][0])#不栽树

dp[i][1] = max(dp[k][1])+val[i]  k = [0,1,2,..,i-1] s.t. lence[i][l]>=lence[k][r]#栽树；所有k的右侧不超过i树左侧的最大值+栽树的价值

初始状态：

dp[0][0] = 0

dp[0][1] = val[0]



def  getmaxvalue(n,po,r,val):
    lence = []
    for i in range(n):
        lence.append([po[i]-r[i],po[i]+r[i]])
    dp = [[0]*2 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = val[0]
    
    for i in range(1,n):
        dp[i][0] = max(dp[i-1][0],dp[i-1][1])    
        for k in range(i):
            if lence[i][0]>=lence[k][1]:
                dp[i][1] = max(dp[i][1],dp[k][1])
        dp[i][1]+=val[i]
    return dp
        


n = 4
po = [2,3,4,5]
r = [1,1,1,2]
val = [50,10,40,70]
print(getmaxvalue(n,po,r,val))


n = 5
po = [2,3,6,5,7]
r = [1,1,3,1,1]
val = [20,20,100,70,60]
print(getmaxvalue(n,po,r,val))