白駿9465号シール(swift)[S 1]

ダイナミックプログラミング(DP)

思想回路.

注意事項

let T = Int(readLine()!)!
var N = 0
var dp = [[Int]]()
var li = [[Int]]()

func sticker(_ c:Int,_ status:Int)->Int{
    
    if c==N{ return 0 }
    if dp[status][c] != -1 { return dp[status][c]}
    
    var ret = sticker(c+1,0) // c번 열에서 아무것도 떼지 않은 경우
    
    if status != 1{ // 위에껄 떼지 않았다면,
        ret = max(ret,sticker(c+1,1)+li[0][c]) //이번에 위에 스티커를 뗀다. 위 스티커 점수 + 위 스티커 뗀 경우의 점수들
    }
    if status != 2{
        ret = max(ret,sticker(c+1,2)+li[1][c]) // 아래 스티커 점수 + 아래 스티커 뗀 경우의 점수
    }
    
    dp[status][c] = ret
    return ret
}


for _ in 0..<T{
    N = Int(readLine()!)!
    
    li = [[Int]]()
    dp = Array(repeating: Array(repeating: -1, count: N), count: 3)
    li.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    li.append(readLine()!.split(separator: " ").map{Int(String($0))!})

    print(sticker(0, 0))
}