스위치를 누른 효과가 j초 남아있는 지속시간 다이나믹 프로그래밍

30460번: 스위치

 

 

i초에 A[i] 점수를 얻는 게임

 

n초간 진행하는데 t초에 스위치를 눌렀을 때 t, t+1, t+2초에는 얻는 점수를 2배로 할 수 있다

 

t초에 스위치를 누르면 t+3초부터 다시 스위치를 누를 수 있다

 

가능한 점수의 최댓값은

 

----------------------------------------------------------------------------------------------------------------------------------------

 

그냥 평소대로 i초간 봤을때 스위치를 눌렀냐 안눌렀냐? dp[i][j]로 j = 0,1 했더니 안풀리더라

 

i초에 눌렀을때 i,i+1,i+2초 점수 2배로 먹는다 쳐도 

 

i초에 안누르고 점수 그대로 가져가도..

 

i초에 눌렀다면 i+3초부터 다시 누를 수 있는데 이게 처리가 잘 안되더라고

 

dp[i][j]를 i초에 스위치의 효과가 j초 남아있을때 얻은 점수의 최댓값이라고 정의하면...

 

처음에 dp[0][0] = A[0]는 스위치를 안누른 경우

 

dp[0][2] = 2*A[0] 스위치를 0초에 처음 눌러서 남은 시간이 2초 남은 경우

 

i = 1부터 n초에 대하여...

 

dp[i][2]는 i초에 스위치를 눌렀으므로, i-1초에는 스위치의 효과가 남아있지 않아야하니

 

dp[i][2] = dp[i-1][0] + 2A[i]

 

dp[i][1]은 i초인 순간에 1초 효과가 남아있으니 i-1초에는 2초 효과가 남아있어야하므로, dp[i-1][2] + 2A[i]

 

dp[i][0]는.... i초인 순간에 효과가 없어야하는데

 

i-1초인 순간에 1초 효과가 남은 경우 dp[i-1][1] + 2A[i]

 

i-1초인 순간에 0초 효과가 남았고 i초에 스위치를 안눌러서 효과가 없는 경우 dp[i-1][0] + A[i]

 

dp[i][0] = max(dp[i-1][1] + 2A[i], dp[i-1][0] + A[i])

 

n = int(input())

A = list(map(int,input().split()))

INF = 10**18

dp = [[-INF]*3 for _ in range(n)]
dp[0][0] = A[0]
dp[0][2] = 2*A[0]

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

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