精進3日目：DPコンテスト C-Vacation - 競プロ引退しました。

自力で解ききれなかった…無念 orz

昨日・今日とうんうん唸って、3回トライしても AC 取れなかったので、先人たちの解答を拝見しました。

考え方

$i$ 日目と、 $i$ 日目に隣接する日の幸福度だけに注目します。そして、 $i$ 日目にa ,b, cそれぞれの活動をした場合に対して、幸福度を求め続ければよいです。

Python3 で実装したコード

# coding: utf-8
import sys
input = sys.stdin.readline

# 1.「今日 a をやったから、昨日は max(b, c) だった」的な考え方。
def dp_happiness(N):
 yesterday_a, yesterday_b, yesterday_c = 0, 0, 0
    for _ in range(N):
        a, b, c = map(int, input().split())

        today_a = a + max(yesterday_b, yesterday_c)
        today_b = b + max(yesterday_c, yesterday_a)
        today_c = c + max(yesterday_a, yesterday_b)

        yesterday_a = today_a
        yesterday_b = today_b
        yesterday_c = today_c
    return max(today_a, today_b, today_c)

# 2.「今日 a をやったから、明日は max(b, c) する」的な考え方。
# def dp_happiness(N):
#     today_a, today_b, today_c = 0, 0, 0
#     for _ in range(N):
#         a, b, c = map(int, input().split())

#         tommorow_a = a + max(today_b, today_c)
#         tommorow_b = b + max(today_c, today_a)
#         tommorow_c = c + max(today_a, today_b)

#         today_a = tommorow_a
#         today_b = tommorow_b
#         today_c = tommorow_c
#     return max(tommorow_a, tommorow_b, tommorow_c)


N = int(input())
print(dp_happiness(N))