AcWing 312. 乌龟棋(Python)
原题链接
简单
作者:
习学学
,
2021-02-09 10:15:34
,
所有人可见
,
阅读 541
Python 代码
N, M = map(int, input().split())
nums = list(map(int, input().split()))
cards = list(map(int, input().split()))
cnt = [0] * 5
for c in cards:
cnt[c] += 1
dp = [[[[0] * (cnt[4]+1) for _ in range(cnt[3]+1)] for _ in range(cnt[2]+1)] for _ in range(cnt[1]+1)]
for A in range(cnt[1]+1):
for B in range(cnt[2]+1):
for C in range(cnt[3]+1):
for D in range(cnt[4]+1):
if A + B*2 + C*3 + D*4 >= N: continue # 防止溢出
score = nums[A + B*2 + C*3 + D*4]
dp[A][B][C][D] = score
if A: dp[A][B][C][D] = max(dp[A][B][C][D], dp[A-1][B][C][D]+score)
if B: dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B-1][C][D]+score)
if C: dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B][C-1][D]+score)
if D: dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B][C][D-1]+score)
print(dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]])