[学習記録]AtCoder EDP C-Vacation[Go]

問題文

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。

夏休みは N 日からなります。 各 i (1≤i≤N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。

• A: 海で泳ぐ。 幸福度 ai​ を得る。

• B: 山で虫取りをする。 幸福度 bi​ を得る。

• C: 家で宿題をする。 幸福度 ci​ を得る。

太郎君は飽き性なので、22 日以上連続で同じ活動を行うことはできません。

太郎君が得る幸福度の総和の最大値を求めてください。

解法

i 日目に 活動Aを行うときの幸福度は、i -1日目に活動B or 活動Cを行った時の最大値に幸福度を足したものになる

// 0 = A, 1 = B, 2 = C
max_a_h := Max(dp[i-1][1], dp[i-1][2])
dp[i][0] = max_a_h + sli[i][0]

活動B, Cについても同様に計算し、N日目まですべて計算する。
N日目の幸福度を計算した後、３つの最大値をとれば回答になる。

ans := Max(Max(dp[n-1][0], dp[n-1][1]), dp[n-1][2])

コード（AC）

func run() interface{} {
	n := readInt()

	sli := make([][]int, n)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		sli[i] = readSli(3)
	}

	// banpei
	dp[0] = make([]int, 3)
	for i := 0; i < 3; i++ {
		dp[0][i] = sli[0][i]
	}

	for i := 1; i < n; i++ {
		dp[i] = make([]int, 3)
		// a=0, b=1, c=2
		max_a_h := Max(dp[i-1][1], dp[i-1][2])
		dp[i][0] = max_a_h + sli[i][0]

		max_b_h := Max(dp[i-1][0], dp[i-1][2])
		dp[i][1] = max_b_h + sli[i][1]

		max_c_h := Max(dp[i-1][1], dp[i-1][0])
		dp[i][2] = max_c_h + sli[i][2]
	}

	ans := Max(Max(dp[n-1][0], dp[n-1][1]), dp[n-1][2])
	return ans