DP C
3つの数列から最も和が大きくなるように取りたい
ただし同じ数列から連続して取ることはできない
直前が3通りのどれであったか、を定義域とし、その場合の和を値とするDP
from 動的計画法
DP_C
PyPy 144 ms
pythondef solve(N, scores):
last_score = scores[0]
for i in range(1, N):
next_score = [
max(last_score[1], last_score[2]) + scores[i][0],
max(last_score[2], last_score[0]) + scores[i][1],
max(last_score[0], last_score[1]) + scores[i][2],
]
last_score = next_score
return max(last_score)Related Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]