Problem:
 Score : 100 points    Problem Statement Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.  The vacation consists of N days.
For each i ( 1 \leq i \leq N ), Taro will choose one of the following activities and do it on the i -th day:   A: Swim in the sea. Gain a_i points of happiness.  B: Catch bugs in the mountains. Gain b_i points of happiness.  C: Do homework at home. Gain c_i points of happiness.   As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.  Find the maximum possible total points of happiness that Taro gains.      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq a_i, b_i, c_i \leq 10^4         Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  a_2  b_2  c_2  :  a_N  b_N  c_N       Output Print the maximum possible total points of happiness that Taro gains.        Sample Input 1 3
10 40 70
20 50 80
30 60 90      Sample Output 1 210  If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.       Sample Input 2 1
100 10 1      Sample Output 2 100       Sample Input 3 7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1      Sample Output 3 46  Taro should do activities in the order C, A, B, A, C, B, A.

Solution (Python):
N = int(input())
activity = [[int(i) for i in input().split()] for _ in range(N)]

dp = [[0, 0, 0] for _ in range(100010)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k: continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j]+activity[i][k])

print(max(dp[N]))

Solution (Python):
N = int(input())
a = [[0 for i in range(3)] for j in range(N)]
dp = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())

for j in range(3):  
    dp[0][j] = a[0][j]

for i in range(1, N):
    dp[i][0] = a[i][0] + max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = a[i][1] + max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = a[i][2] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[N-1]))

Solution (Python):
N = int(input())
a = [[0 for i in range(3)] for j in range(N)]
dp = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())

for j in range(3):  
    dp[0][j] = a[0][j]

for i in range(1, N):
    dp[i][0] = a[i][0] + max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = a[i][1] + max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = a[i][2] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for i in range(n)]

dp = [[0,0,0] for _ in range(n)]
dp[0] = abc[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + abc[i][0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + abc[i][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + abc[i][2]

ans = max(dp[n-1])

print(ans)

Solution (Python):
n = int(input())

dp = [[0]*3 for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

for i in range(1,n):
    l = [int(x) for x in input().split()]
    for j in range(3):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + l[j]

print(max(dp[n-1]))

Solution (Python):
n = int(input())

dp = [[0]*3 for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

for i in range(1,n):
    l = list(map(int, input().split()))
    for j in range(3):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + l[j]

print(max(dp[n-1]))

Solution (Python):
N = int(input())
ABC = [list(map(int,input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(3):
    dp[i][j] = max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]) + ABC[i-1][j]
print(max(dp[-1]))

Solution (Python):
n = int(input())
v = [list(map(int, input().split())) for _ in range(n)]

dp = [[0, 0, 0] for _ in range(n + 5)]
for i in range(1, n + 1):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + v[i - 1][0]
    dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + v[i - 1][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + v[i - 1][2]
print(max(dp[n]))

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    dp = [[0] * 3 for _ in range(n)]
    for i in range(n):
        a, b, c = list(map(int, readline().split()))
        if i == 0:
            dp[i][0] = a
            dp[i][1] = b
            dp[i][2] = c
        else:
            dp[i][0] = max(dp[i-1][1] + a, dp[i-1][2] + a)
            dp[i][1] = max(dp[i-1][0] + b, dp[i-1][2] + b)
            dp[i][2] = max(dp[i-1][0] + c, dp[i-1][1] + c)
    print(max(dp[-1]))


if __name__ == '__main__':
    solve()

Solution (Python):
N = int(input())

h = [[0, 0, 0] for i in range(N + 1)]


for i in range(1, N + 1):
    a, b, c = map(int, input().split())
    
    h[i][0] = max(h[i - 1][1] + a, h[i - 1][2] + a)
    h[i][1] = max(h[i - 1][0] + b, h[i - 1][2] + b)
    h[i][2] = max(h[i - 1][0] + c, h[i - 1][1] + c)

print(max(h[N]))

Solution (Python):
import sys

input = sys.stdin.readline

N = int(input())    
K = 3      

acts = []   
for _ in range(N):
  acts.append(list(map(int, input().split())))






inf = 1e10
dp_list = [[-inf for _ in range(K)] for __ in range(N)]


for i in range(K):
  dp_list[0][i] = acts[0][i]

for day in range(1,N):
  for act in range(K):
    for act_possible in range(K):
      if act == act_possible:
        continue
      dp_list[day][act] = max(dp_list[day][act], dp_list[day-1][act_possible] + acts[day][act])

print(max(dp_list[-1]))

Solution (Python):
def solve():
    N = int(input())
    happiness = [[0] * 3 for i in range(N)]
    for i in range(N):
        tmpa, tmpb, tmpc = map(int, input().split())
        happiness[i][0] = tmpa
        happiness[i][1] = tmpb
        happiness[i][2] = tmpc

    dp = [[0] * 3 for i in range(N+1)]

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

    print(max(dp[-1][0], dp[-1][1], dp[-1][2]))
            

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
nes = [list(map(int,input().split())) for i in range(N)]
A = [0]
B = [0]
C = [0]
for i in range(N) :
    a = nes[i][0] + max(B[-1],C[-1])
    b = nes[i][1] + max(A[-1],C[-1])
    c = nes[i][2] + max(B[-1],A[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1],B[-1],C[-1]))

Solution (Python):
n = int(input())
data = []
a=0
b=1
c=2
dp = [[0 for i in range(3)] for j in range(n)]
for i in range(n):
    data.append(list(map(int, input().split())))

dp[0][a]=data[0][a]
dp[0][b]=data[0][b]
dp[0][c]=data[0][c]
for i in range(1,n):
    dp[i][a]=data[i][a]+max(dp[i-1][b],dp[i-1][c])
    dp[i][b]=data[i][b]+max(dp[i-1][a],dp[i-1][c])
    dp[i][c]=data[i][c]+max(dp[i-1][a],dp[i-1][b])
print(max(dp[-1][a],dp[-1][b],dp[-1][c]))

Solution (Python):
n = int(input())
hh = []
for i in range(n):
    h = list(map(int, input().split()))
    hh.append(h)

c = [[0 for j in range(3)] for i in range(n)]
for i in range(3):
    c[0][i]  = hh[0][i]

for i in range(1,n):
    c[i][0] = max(c[i-1][1], c[i-1][2]) + hh[i][0]
    c[i][1] = max(c[i-1][0], c[i-1][2]) + hh[i][1]
    c[i][2] = max(c[i-1][0],c[i-1][1]) + hh[i][2]
print(max(c[-1]))

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def wakacje(): 
    N = wczytaj_liste()[0]
    punkty_za_zadania = [None]*N
    for i in range(N):
        punkty_za_zadania[i] = wczytaj_liste()
    wczoraj = [0, 0, 0]
    dzisaj = [None]*3
    for i in range(N):
        dzisaj[0] = max(wczoraj[1]+punkty_za_zadania[i][0], wczoraj[2]+punkty_za_zadania[i][0])
        dzisaj[1] = max(wczoraj[0]+punkty_za_zadania[i][1], wczoraj[2]+punkty_za_zadania[i][1])
        dzisaj[2] = max(wczoraj[0]+punkty_za_zadania[i][2], wczoraj[1]+punkty_za_zadania[i][2])
        wczoraj = dzisaj[:]
    print (max(wczoraj))
    
wakacje()

Solution (Python):
N = int(input())
A = [0]*N
B = [0]*N
C = [0]*N
for i in range(N):
    a,b,c = map(int, input().split())
    A[i] = a
    B[i] = b
    C[i] = c
    
dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = A[0]
dpb[0] = B[0]
dpc[0] = C[0]

for i in range(1, N):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + A[i]
    dpb[i] = max(dpc[i-1], dpa[i-1]) + B[i]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + C[i]
    
print(max(dpa[-1], dpb[-1], dpc[-1]))

Solution (Python):
INF = float('inf')
N = int(input())
H = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + H[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i])

print(ans)

Solution (Python):
n=int(input())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split() )

z=[[0,0,0] for _ in range(n)]
z[0]=[a[0], b[0], c[0]]
for i in range(1, n):
    z[i][0]=max(a[i]+z[i-1][1], a[i]+z[i-1][2])
    z[i][1]=max(b[i]+z[i-1][0], b[i]+z[i-1][2])
    z[i][2]=max(c[i]+z[i-1][0], c[i]+z[i-1][1])

print(max(z[-1]))

Solution (Python):
n=int(input())
prev=[0,0,0]
for i in range(n):
    dp=[0,0,0]
    c=list(map(int,input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                dp[i]=max(dp[i],prev[j]+c[i])
    prev=dp[:]
print(max(prev))

Solution (Python):
N=int(input())
A=[]

dp=[[0 for i in range(3)] for j in range(N+1)]


for i in range(N):
    B,C, D = map(int, input().split())
    A.append([B,C, D])


for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][k]=max(dp[i+1][k],dp[i][j]+A[i][k])

print(max(dp[N][0],dp[N][1],dp[N][2]))

Solution (Python):
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * (n+1) for i in range(3)]

for i in range(n):
    dp[0][i+1] = max(dp[1][i], dp[2][i]) + info[i][0]
    dp[1][i+1] = max(dp[2][i], dp[0][i]) + info[i][1]
    dp[2][i+1] = max(dp[0][i], dp[1][i]) + info[i][2]

print(max(dp[0][n], dp[1][n], dp[2][n]))

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*3 for _ in range(n)]
for i in range(3):
    dp[0][i] = abc[0][i]
for i in range(1, n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][j] = max(dp[i][j], dp[i-1][k]+abc[i][j])
print(max(dp[-1]))

Solution (Python):
def main():
    N = int(input())
    dp = [[0] * 3 for _ in range(N+1)]
    for i in range(1, N+1):
        
        happiness = [int(i) for i in input().split()]
        
        for j in range(3):
            
            for k in range(3):
                
                if j == k:
                    continue
                
                dp[i][k] = max(dp[i][k], dp[i-1][j] + happiness[k])
    ans = max(dp[-1])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
ABC= [list(map(int,input().split())) for i in range(n)]

A=[0]*n
B=[0]*n
C=[0]*n
A[0],B[0],C[0]=ABC[0]
for i in range(1,n):
    A[i]=max(B[i-1],C[i-1])+ABC[i][0]
    B[i]=max(A[i-1],C[i-1])+ABC[i][1]
    C[i]=max(B[i-1],A[i-1])+ABC[i][2]
print(max(A[n-1], B[n-1],C[n-1]))

Solution (Python):
n=int(input())
a,b,c=map(int,input().split())
ref=[a,b,c]
for i in range(n-1):
 a,b,c=map(int,input().split())
 ref1=[0,0,0]
 ref1[0]=max(ref[1]+a,ref[2]+a)
 ref1[1]=max(ref[0]+b,ref[2]+b)
 ref1[2]=max(ref[0]+c,ref[1]+c)
 ref=ref1
print(max(ref))

Solution (Python):



N = int(input())
dp = [[0, 0, 0] for i in range(N)]
H = []


for i in range(N):
    l = list(map(int, input().split()))
    H.append(l)

dp[0] = [H[0][0], H[0][1], H[0][2]]

for i in range(1, N):
    
    for k in range(3):
        
        for j in range(3):
            if j == k:
                continue
            else:
                dp[i][j] = max(dp[i][j], (dp[i - 1][k] + H[i][j]))
print(max(dp[N - 1]))

Solution (Python):
N = int(input())
ABC = [list(map(int,input().split())) for _ in range(N)]


dp = [[0] * 3 for _ in range(N+2)]

for i in range(1,N+1):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + ABC[i-1][0]
    dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + ABC[i-1][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + ABC[i-1][2]

print(max(dp[N]))

Solution (Python):
import sys
import numpy as np

n = int(input())
days = []
for _ in range(n):
    day = list(map(int, input().split()))
    days.append(day)
dp = [[10000] * 3 for _ in range(n)]


dp[0][0] = days[0][0]
dp[0][1] = days[0][1]
dp[0][2] = days[0][2]


for d in range(1,n):
    for i in range(3):
        mx = 0
        for j in range(3):
            if i != j:
                mx = max(dp[d-1][j] + days[d][i],mx)
                
        dp[d][i] = mx
print(max(dp[-1]))

Solution (Python):
N = int(input())
days = [list(map(int, input().split())) for i in range(N)]

dp = [[0]*3 for i in range(N + 1)]
for i in range(N):
    for k in range(3):
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][(k + 1) % 3] + days[i][k], dp[i][(k - 1) % 3] + days[i][k])

print(max(dp[-1]))

Solution (Python):
N = int(input())
L = []

for i in range(N):
  l = list(map(int,input().split()))
  L.append(l)
  
dp = [[0,0,0] for i in range(N)]
dp[0] = [L[0][0],L[0][1],L[0][2]]

for i in range(1,N):
  for j in range(3):
    dp[i][j] = max(dp[i - 1][(j + 1) % 3],dp[i - 1][(j + 2) % 3]) + L[i][j]
    
print(max(dp[N - 1]))

Solution (Python):
"""
NTC here
"""
import sys
input= sys.stdin.readline




def iin(): return int(input())
def lin(): return list(map(int, input().split()))




def main():
    n = iin()
    Q = [lin() for i in range(n)]
    ans = [[0, 0, 0] for i in range(n+1)] 
   
    for i in range(n-1, -1, -1):
        for j in range(3):
            ans[i][j]=Q[i][j]+max([
                ans[i+1][k] for k in range(3) if k!=j
            ])
  
    print(max(ans[0]))

        



                









        
main()

Solution (Python):

 
import math
import itertools
import sys
 


N = int(input())
V = []
for _ in range(N) :
  S = str(input())
  V.append(list(map(int, S.split())))




dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(N) :
  if i == 0 :
      dp[i][0] = V[i][0]
      dp[i][1] = V[i][1]
      dp[i][2] = V[i][2]
  else :
      dp[i][0] = V[i][0] + max(dp[i-1][1], dp[i-1][2])
      dp[i][1] = V[i][1] + max(dp[i-1][0], dp[i-1][2])
      dp[i][2] = V[i][2] + max(dp[i-1][0], dp[i-1][1])



print (max(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

Solution (Python):
N = int(input())
abc = [[]]
for i in range(N):
    abc.append(list(map(int, input().split())))

dp = [[0,0,0] for _ in range(N+1)]
dp[1] = [abc[1][0], abc[1][1], abc[1][2]]
for i in range(2, N+1):
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]) + abc[i][j]
print(max(dp[N]))

Solution (Python):
N = int(input())
abc = [[int(i) for i in input().split()] for j in range(N)]
dp = [abc[0]]  
for i in range(1, N):
    ith_day = [
        max(dp[-1][1], dp[-1][2]) + abc[i][0],
        max(dp[-1][2], dp[-1][0]) + abc[i][1],
        max(dp[-1][0], dp[-1][1]) + abc[i][2],
    ]
    dp.append(ith_day)
print(max(dp[-1]))

Solution (Python):
import sys

def resolve():
        input = sys.stdin.readline
        N=int(input().rstrip())

        A=[[0] * 3 for i in range(N)]
        for i in range(N):
            A[i][:]=list(map(int,input().rstrip().split()))

        dp=[[0] * 3 for i in range(N)]
        for j in range(3):
            dp[0]=A[0]

        for i in range(1,N,1):
            for j in range(3):
                for k in range(3):
                    if(k!=j):
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+A[i][j])
       
        print(max(dp[N-1]))
          
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
10 40 70
20 50 80
30 60 90"""
        output = """210"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1
100 10 1"""
        output = """100"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1"""
        output = """46"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
n = int(input())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [[0 for x in range(3)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if k != j:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i - 1][j])
print(max(dp[n]))

Solution (Python):
N = int(input())

dp = [[0, 0, 0] for _ in range(N)]
a, b, c = map(int, input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

for i in range(1, N):
    a, b, c = map(int, input().split())

    dp[i][0] = max(dp[i][0], dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i][1], dp[i - 1][0] + b, dp[i - 1][2] + b)
    dp[i][2] = max(dp[i][2], dp[i - 1][0] + c, dp[i - 1][1] + c)

print(max(dp[N - 1]))

Solution (Python):
def main():

    n = int(input())
    
    dp = [0] * 3
    
    for day in range(n):
        new_dp = [0] * 3
        activities = [int(x) for x in input().split()]
        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + activities[j])
        dp = new_dp
    print(max(dp))


main()

Solution (Python):
def main():

    n = int(input())
    activities = [[int(x) for x in input().split()] for _ in range(n)]
    dp = [0] * 3
    
    for day in range(n):
        new_dp = [0] * 3
        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + activities[day][j])
        dp = new_dp
    print(max(dp))


main()

Solution (Python):
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n)]
dp[0] = arr[0]


for i in range(1, n):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
print (max(dp[-1]))

Solution (Python):

N = int(input())
hap = []
for i in range(N):
	abc = list(map(int, input().split()))
	hap.append(abc)

dp = []
for i in range(N):
	dp.append([0,0,0])

dp[0] = hap[0]

for x in range(N-1):
	i = x+1
	dp[i][0] = hap[i][0]+max(dp[i-1][1], dp[i-1][2])
	dp[i][1] = hap[i][1]+max(dp[i-1][0], dp[i-1][2])
	dp[i][2] = hap[i][2]+max(dp[i-1][0], dp[i-1][1])

print(max(dp[N-1]))

Solution (Python):
N = int(input())
DP = [[0]*3]*N
abc = [0] * N
for i in range(N):
    L = list(map(int,input().split()))
    abc[i] = L
for i,value in enumerate(abc):
    dp = [0]*3
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[k] = max(dp[k],DP[i-1][j] + value[k])
    DP[i] = dp
print(max(DP[-1]))

Solution (Python):
N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]

dp[0] = [a[0], b[0], c[0]]
for i in range(N - 1):
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1], dp[i][2] + a[i + 1])
    dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1], dp[i][2] + b[i + 1])
    dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1], dp[i][1] + c[i + 1])
print(max(dp[N - 1]))

Solution (Python):
N = int(input())
ABC = [list(map(int,input().split())) for _ in range(N)]
hap = [[0,0,0] for _ in range(N)]
hap[0] = ABC[0]
for j in range(1,N):
  for i1,i2,i3 in [[0,1,2],[1,2,0],[2,0,1]]:
    hap[j][i2] = max(hap[j][i2], hap[j-1][i1]+ABC[j][i2])
    hap[j][i3] = max(hap[j][i3], hap[j-1][i1]+ABC[j][i3])
print(max(hap[-1][:]))

Solution (Python):
N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N)]


for j in range(3):
    dp[0][j] = ABC[0][j]


for i in range(1, N):
    a, b, c = ABC[i]
    dp[i][0] = max(dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i - 1][0] + b, dp[i - 1][2] + b)
    dp[i][2] = max(dp[i - 1][1] + c, dp[i - 1][0] + c)
print(max(dp[-1]))

Solution (Python):
import sys


def main(N, matrix):
    row = len(matrix)
    col = len(matrix[0])
    res = []
    for i in range(row):
        res.append([0] * col)
    for action in range(3):
        res[0][action] = matrix[0][action]

    for day in range(1, N):
        for action in range(3):
            res[day][action] = matrix[day][action]
            for prev_action in [a for a in range(3) if a != action]:
                res[day][action] = max(res[day][action], res[day-1][prev_action] + matrix[day][action])

    print max(res[N - 1])


if __name__ == '__main__':
  N, matrix = None, []
  matrix = []
  for i, line_ in enumerate(sys.stdin):
    line = line_.strip()
    if line:
        if not i:
            N = int(line.strip())
        else:
            H = map(int, line.strip().split())
            matrix.append(H)
  if N is not None and matrix:
    main(N, matrix)

Solution (Python):
def calc_happiness(h):
    n = len(h)

    states = [[None, None, None] for i in range(n)]
    states[0] = h[0]
    for i in range(1, n):
        states[i][0] = h[i][0] + max(states[i-1][1], states[i-1][2])
        states[i][1] = h[i][1] + max(states[i-1][0], states[i-1][2])
        states[i][2] = h[i][2] + max(states[i-1][0], states[i-1][1])
    return max(states[n-1][0], states[n-1][1], states[n-1][2])

if __name__ == "__main__":
    n = int(input())
    h = [[]] * n
    for day in range(n):
        h[day] = list(map(int, input().split(" ")))
    res = calc_happiness(h)
    print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def vacation(n, cost):
    res = []
    for i in range(n):
        res.append([-1,-1,-1])

    for i in range(3):
        res[0][i] = cost[0][i]
        for day in range (1, n ):
            for action in range(3):
                res[day][action] = cost[day][action]
                for prev_action in range(3):
                    if prev_action == action:
                        continue
                    res[day][action] = max(res[day][action], res[day-1][prev_action] + cost[day][action])
    
    
    
    print(max(res[n-1]))

def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    gains = lines[1:]
 
    
    
    vacation(n, gains)


if __name__ == '__main__':
    main()

Solution (Python):



def solution():
    
    res = [[-1 for x in range(3)] for y in range(n)]
    res[0] = a[0]
    for i in range(1,n):
        
        for j in range(3):
            
            
            
            

            
            bph = -1
            for o in range(3):
                
                if o==j:
                    continue
                bph = max(bph, res[i-1][o])
            
            
            res[i][j] = max(res[i][j], bph + a[i][j])

    return max(res[-1][0],res[-1][1],res[-1][2])


if __name__ == "__main__":
    n = int(input())

    a = [[None for x in range(3)] for y in range(n)]

    for i in range(n):
        row = list(map(int, input().split(" ")))
        for j in range(3):
            a[i][j] = row[j]

    
    if n == 1:
        print(max(a[0][0],a[0][1],a[0][2]))
    else:
        print(solution())

Solution (Python):
def vacation(n, cost):
    res = [[0]*3 for i in range(n)]
    for i in range(3):
        res[0][i] = cost[0][i]
    for d in range(1, n):
        for a in range(3):
            res[d][a] = cost[d][a]
            for pa in range(3):
                if pa != a:
                    res[d][a] = max(res[d][a], res[d-1][pa]+cost[d][a])
    return max(res[-1])

def main():
    n = int(input())
    cost = [[0, 0, 0]]*n
    for i in range(n):
        cost[i] = list(map(int, input().split()))

    print(vacation(n, cost))

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*3 for i in range(n)]
dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

for j in range(n-1):
    dp[j+1][0] = max(dp[j][1],dp[j][2])+abc[j+1][0]
    dp[j+1][1] = max(dp[j][0],dp[j][2])+abc[j+1][1]
    dp[j+1][2] = max(dp[j][0],dp[j][1])+abc[j+1][2]
print(max(dp[n-1]))

Solution (Python):
N=int(input())
labc=[]
for i in range(N):
    labc.append(list(map(int,input().split())))
ldp=[[0,0,0] for i in range(N)]
ldp[0][0]=labc[0][0]
ldp[0][1]=labc[0][1]
ldp[0][2]=labc[0][2]
for i in range(1,N):
    ldp[i][0]=max(ldp[i-1][1],ldp[i-1][2])+labc[i][0]
    ldp[i][1]=max(ldp[i-1][2],ldp[i-1][0])+labc[i][1]
    ldp[i][2]=max(ldp[i-1][0],ldp[i-1][1])+labc[i][2]
print(max(ldp[N-1]))

Solution (Python):
n = int(input())
a=[]
b=[]
c=[]
for i in range(n):
    tmpa,tmpb,tmpc = map(int,input().split())
    a.append(tmpa)
    b.append(tmpb)
    c.append(tmpc)


dp = [[0 for i in range(3)] for j in range(n+1)]

for i in range(1,n+1):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i-1]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i-1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i-1]

print(max(dp[n][0],dp[n][1],dp[n][2]))

Solution (Python):
INF = float("inf") 
MOD = 10**9+7 
MAX = 510000 

def main():
    n = int(input())
    h = [list(map(int,input().split())) for i in range(n)]
    dp = [[0]*3 for i in range(n+1)]

    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j!=k:
                    dp[i+1][k] = max(dp[i+1][k],dp[i][j]+h[i][k])

    ans = 0
    for i in range(3):
        ans = max(ans,dp[n][i])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
INF = int(1e10)

N = int(input())
A, B, C = [None], [None], [None]

for _ in range(N):
    a, b, c = list(map(int, input().split()))
    A.append(a)
    B.append(b)
    C.append(c)


DP = [[0 for _ in range(3)] for _ in range(N + 1)]
DP[1][0] = A[1]
DP[1][1] = B[1]
DP[1][2] = C[1]


for d in range(2, N + 1):
    
    DP[d][0] = max(DP[d-1][1], DP[d-1][2]) + A[d]
    DP[d][1] = max(DP[d-1][0], DP[d-1][2]) + B[d]
    DP[d][2] = max(DP[d-1][0], DP[d-1][1]) + C[d]

print(max(DP[N][:]))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
act = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N)]
dp[0][0] = act[0][0]
dp[0][1] = act[0][1]
dp[0][2] = act[0][2]
for i in range(N - 1):
  for j in range(3):
    dp[i + 1][j] = max(dp[i][(j + 1) % 3], dp[i][(j + 2) % 3]) + act[i + 1][j]
print(max(dp[-1]))

Solution (Python):
N = int(input())
abcList = [list(map(int, input().split())) for i in range(N)]
dp = [abcList[0]]

if len(abcList) == 1:
    print(max(abcList[0][0], abcList[0][1], abcList[0][2]))
else:
    for i in range(1, N):
        dp.append([abcList[i][0] + max(dp[i - 1][1], dp[i - 1][2]),
                   abcList[i][1] + max(dp[i - 1][0], dp[i - 1][2]),
                   abcList[i][2] + max(dp[i - 1][0], dp[i - 1][1])])
    print(max(dp[-1]))

Solution (Python):


N = int(input())
a,b,c = [],[],[]
for _ in range(N):
	ai,bi,ci = map(int, input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)

def mymax(a,b):
	if a>b:
		return a
	else:
		return b
		
dp = [[0]*(N+1) for _ in range(3)]

first_day = max([a[0],b[0],c[0]])
for i in range(3):
	dp[i][1] = first_day
	
for n in range(2, N+1):
	dp[0][n] = mymax(dp[1][n-1]+b[n-1], dp[2][n-1]+c[n-1])
	dp[1][n] = mymax(dp[0][n-1]+a[n-1], dp[2][n-1]+c[n-1])
	dp[2][n] = mymax(dp[0][n-1]+a[n-1], dp[1][n-1]+b[n-1])

ans = 0
for i in range(3):
	if dp[i][N] > ans:
		ans = dp[i][N]
print(ans)

Solution (Python):
n = int(input())
lst = [list(map(int, input().split())) for i in range(n)]

dp = [lst[0]] + [[0] * 3 for i in range(n - 1)]

for i in range(1, n):
    for j in range(3):
        for k in range(3):
            if j == k:
                pass
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + lst[i][j])

print(max(dp[n - 1]))

Solution (Python):

dp=[0,0,0]
n=int(input())
for i in range(n):
    a,b,c=map(int,input().split())
    
    dp = [max(dp[1],dp[2])+a, 
          max(dp[0],dp[2])+b,
          max(dp[1],dp[0])+c]
print(max(dp))
"""
i 日目にとりうる選択肢が何通りかあって、
愚直に全探索すると O(2n)O(2n) とか O(3n)O(3n) とか O(Kn)O(Kn) とかになる場面では
「dp[ i ] := 最初の i 日間での最適解」の形の DPの検討はアリ。
"""

Solution (Python):
n = int(input())
S = []
for _ in range(n):
    A = list(map(int, input().split()))
    S.append(A)

Dp = [[] for _ in range(n)]


for i in range(3):
    Dp[0].append(S[0][i])

for i in range(1, n):
    
    for j in range(3):
        
        New_Dp = []
        
        for k in range(3):
            if j==k:
                continue
            else:
                new_dp = Dp[i-1][k] + S[i][j]
                New_Dp.append(new_dp)
        dp = max(New_Dp)
        Dp[i].append(dp)

ans = max(Dp[-1])
print(ans)

Solution (Python):
from sys import stdin,stdout

n = int(stdin.readline())
a = []
for i in range(n):
    x,y,z = map(int,stdin.readline().split())
    a.append([x,y,z])
dp = [[0,0,0] for i in range(n)]
dp[0] =  [a[0][0],a[0][1],a[0][2]] 
for i in range(1,n):
    dp[i][0] = a[i][0] + max( dp[i-1][1],dp[i-1][2] )
    dp[i][1] = a[i][1] + max( dp[i-1][0],dp[i-1][2] )
    dp[i][2] = a[i][2] + max( dp[i-1][0],dp[i-1][1] )
ans = max(dp[n-1])
stdout.write(str(ans))

Solution (Python):
n = int(input())
prevA, prevB, prevC = 0, 0, 0
for i in range(n):
    a,b,c = map(int, input().split())
    act_a_on_ith_day = a + max(prevB, prevC)
    act_b_on_ith_day = b + max(prevA, prevC)
    act_c_on_ith_day = c + max(prevA, prevB)
    prevA, prevB, prevC = act_a_on_ith_day, act_b_on_ith_day, act_c_on_ith_day
print(max(prevA, prevB, prevC))

Solution (Python):
N = int(input())
a = [tuple(map(int, input().split())) for i in range(N)]

dp = [[0] * 3 for i in range(N + 1)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][j] = max(dp[i+1][j], dp[i][k]+a[i][j])

print(max(dp[N]))

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]
for i in range(N):
    dp[i+1][0] = max(dp[i][1]+abc[i][0], dp[i][2]+abc[i][0])
    dp[i+1][1] = max(dp[i][0]+abc[i][1], dp[i][2]+abc[i][1])
    dp[i+1][2] = max(dp[i][0]+abc[i][2], dp[i][1]+abc[i][2])
print(max(dp[-1]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

dp1 = abc[0]
dp2 = [0, 0, 0]

for i in range(1, n):
    dp2[0] = abc[i][0] + max(dp1[1], dp1[2])
    dp2[1] = abc[i][1] + max(dp1[0], dp1[2])
    dp2[2] = abc[i][2] + max(dp1[0], dp1[1])
    dp1 = dp2
    dp2 = [0, 0, 0]

print(max(dp1))

Solution (Python):
N = int(input())
activity = [[0, 0, 0] for _ in range(10**5+10)]

for i in range(N):
    activity[i] = [int(i) for i in input().split()]

dp = [[0, 0, 0] for _ in range(10**5+10)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k: continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + activity[i][k])

print(max(dp[N]))