Let \(f(i, j)\) be the maximum happiness that Taro gains in the first \(i\) days if he chooses activity \(j\) on the \(i\)-th day. Here, tracking activity \(j\) is necessary to avoid choosing the same activity across consecutive days. We also define sentinel values \(f(0, \text{A})=f(0, \text{B})=f(0, \text{C})=0\).

If Taro chooses activity A on the \(i\)-th day, his choice for the \((i-1)\)-th day can only be activities B or C, so

\[f(i, \text{A})=a_i+\max(f(i-1,\text{B}),f(i-1,\text{C})).\]

We can similarly define \(f(i, \text{B})\) and \(f(i, \text{C})\). The answer to the original problem is the maximum of \(f(N, \text{A})\), \(f(N, \text{B})\) and \(f(N, \text{C})\).

Thus, by iterating over values of \(i\), we can implement a solution that runs in \(O(N)\) time.

Sample code (Python):

N = int(input())
happiness = [[int(x) for x in input().split()] for _ in range(N)]

dp = [[0, 0, 0] for _ in range(N + 1)]
for i in range(N):
    for j in range(3):
        dp[i + 1][j] = (
            happiness[i][j]
            + max(dp[i][k] for k in range(3) if j != k)
        )

print(max(dp[-1]))

The above implementation uses \(O(N)\) space to store results for all \(N\) days in the dp array. Since we only need results from the previous day, we can modify the code to use \(O(1)\) space by only storing results from the last two days.

Sample code (Python):

N = int(input())
happiness = [[int(x) for x in input().split()] for _ in range(N)]

dp = [0, 0, 0]
for i in range(N):
    ndp = [0, 0, 0]
    for j in range(3):
        ndp[j] = (
            happiness[i][j]
            + max(dp[k] for k in range(3) if j != k)
        )
    dp = ndp

print(max(dp))