DP C
C - Vacation
I want to take the greatest sum from three sequences of numbers.
However, they cannot be taken consecutively from the same sequence of numbers.
The definition region is which of the three ways was the immediate previous one, and the value is the sum of the three cases.
from dynamic programming
DP_C
PyPy 144 ms
code:python
def solve(N, scores):
last_score = scores0
for i in range(1, N):
next_score = [
max(last_score1, last_score2) + scoresi0,
max(last_score2, last_score0) + scoresi1,
max(last_score0, last_score1) + scoresi2,
]
last_score = next_score
return max(last_score)
---
This page is auto-translated from /nishio/DP C. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.