問題
回答
動的計画法を使って解く。
貰うDP
ノード i への遷移方法を考える。
つまり、 dp[ i – 1 ] の値がわかっているときに、dp[ i ] の値を更新する。
ただし、i – 1日に取った行動が i 日に取れる行動を制限するので、行動をjとして、dp[ i ] を、dp[ i ][ j ] と拡張する。
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
# dpの最大値を更新するための関数
def chmax(a, b):
if a > b:
return a
else:
return b
# dp[i-1][0] から dp[i][1] への遷移
# dp[i-1][0] から dp[i][2] への遷移
# dp[i-1][1] から dp[i][0] への遷移
# dp[i-1][1] から dp[i][2] への遷移
# dp[i-1][2] から dp[i][0] への遷移
# dp[i-1][2] から dp[i][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i][k], dp[i-1][j] + lst_happiness[i-1][k])
for i in range(1, vacation+1):
for j in range(3):
for k in range(3):
if j == k:
continue
dp[i][k] = chmax(dp[i][k], dp[i-1][j] + lst_happiness[i-1][k])
ans = 0
for i in range(3):
ans = chmax(ans, dp[vacation][i])
print(ans)
配るDP
ノード i からの遷移方法を考える。
つまり、 dp[ i ] の値がわかっているときに、dp[ i + 1 ] の値を更新する。
ただし、i 日に取った行動が i+1 日に取れる行動を制限するので、行動をjとして、dp を、dp[ i ][ j ] と拡張する。
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
if a > b:
return a
else:
return b
# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
for j in range(3):
for k in range(3):
if j == k:
continue
dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
ans = chmax(ans, dp[vacation][i])
print(ans)
メモ化再帰
再帰関数を使って解く。
すでに分かっている値をメモしておくことで、計算時間を節約する。
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
# dpの最大値を更新するための関数
def chmax(a, b):
if a > b:
return a
else:
return b
# メモ化再帰の関数
def rec(i):
# DPの値が既に更新されている場合はその値を返す
for j in range(3):
if dp[i][j] > 0:
break
# 再帰の終了条件
if i == 0:
dp[i][j] = 0
break
# i-1 を再帰
res = 0
for k in range(3):
if j == k:
continue
res = chmax(res, rec(i-1)[k] + lst_happiness[i-1][k])
# 結果をメモする
dp[i][j] = res
return dp[i]
ans = rec(vacation)
ans = max(ans)
print(ans)
numpy
numpy を使って解く。
import sys
import numpy as np
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# lst_happinessをndarrayにする。
arr_happiness_a = np.array([lst_happiness[i][0] for i in range(vacation)])
arr_happiness_b = np.array([lst_happiness[i][1] for i in range(vacation)])
arr_happiness_c = np.array([lst_happiness[i][2] for i in range(vacation)])
# DPのndarrayを作る。
dp_a = np.zeros(vacation, dtype=int)
dp_b = np.zeros(vacation, dtype=int)
dp_c = np.zeros(vacation, dtype=int)
# dpに初期値を入れる。
dp_a[0] = arr_happiness_a[0]
dp_b[0] = arr_happiness_b[0]
dp_c[0] = arr_happiness_c[0]
for i in range(1, vacation):
dp_a[i] += max(dp_b[i-1], dp_c[i-1]) + arr_happiness_a[i]
dp_b[i] += max(dp_a[i-1], dp_c[i-1]) + arr_happiness_b[i]
dp_c[i] += max(dp_a[i-1], dp_b[i-1]) + arr_happiness_c[i]
ans = max(dp_a[vacation-1], dp_b[vacation-1], dp_c[vacation-1])
print(ans)