AcWing 312. 乌龟棋
原题链接
简单
作者:
不知名_4
,
2024-04-11 15:08:45
,
所有人可见
,
阅读 1
Python 代码
n , m = map(int,input().split())
arr = [0,]
tmp = list(map(int,input().split()))
arr.extend(tmp)
card = list(map(int,input().split()))
# print(arr)
A,B,C,D = 0,0,0,0
for i in card:
if i==1:
A += 1
elif i == 2:
B += 1
elif i==3:
C += 1
elif i==4:
D += 1
# 用完所有的爬行卡一定会到达终点,
# 到达终点的所使用的最后一张卡是 1/ 2/ 3/ 4中的一张(A\B\C\D表示)
# 由此得到状态转移方程 f[a][b][c][d] = max(f[a-1][b][c][d],f[a][b-1][c][d],f[a][b][c-1][d],f[a][b][c][d-1]) + arr[1+a+2*b+3*c+4*d]
f = [[[[0 for i in range(D+1)] for i in range(C+1)] for i in range(B+1)] for i in range(A+1)]
# if A>0:
# f[1][0][0][0] = arr[1+1]
# if B>0:
# f[0][1][0][0] = arr[1+2]
# if C>0:
# f[0][0][1][0] = arr[1+3]
# if D>0:
# f[0][0][0][1] = arr[1+4]
# print(f)
for a in range(A+1):
for b in range(B+1):
for c in range(C+1):
for d in range(D+1):
# if a-1>=0 and b-1>=0 and c-1>=0 and d-1>=0 :
# f[a][b][c][d] = max(f[a-1][b][c][d],f[a][b-1][c][d],f[a][b][c-1][d],f[a][b][c][d-1]) + arr[1+a+2*b+3*c+4*d]
score = arr[1+a+2*b+3*c+4*d]
#只有A B C D对应的爬行卡数大于零,我们才需要考虑
if A>0:
f[a][b][c][d] = max(f[a][b][c][d],f[a-1][b][c][d] + score)
if B>0:
f[a][b][c][d] = max(f[a][b][c][d],f[a][b-1][c][d] + score)
if C>0:
f[a][b][c][d] = max(f[a][b][c][d],f[a][b][c-1][d] + score)
if D>0:
f[a][b][c][d] = max(f[a][b][c][d],f[a][b][c][d-1] + score)
print(f[A][B][C][D])