package main import . "fmt" import . "os" import bf "bufio" func main() { rd := bf.NewReader(Stdin) var n int Fscan(rd,&n) p := make([]int, n) a := make([]int, n) for i := range a { Fscan(rd,&p[i],&a[i]) } dp := make([]int, 2) dp[0] = p[n-1] dp[1] = a[n-1] for i := n-2; i >= 0; i-- { dp[0],dp[1] = p[i]+max(dp[0],dp[1]),a[i]+max(dp[0]+p[i+1],dp[1]+a[i+1]) } Println(max(dp[0],dp[1])) } /* 考察 難しい たぶん、おそらく Nゲーム目から逆順にDPかなあ…? DP[i本目][i本目でpi本倒したかai本倒したかの2択] DP[i][p] = p[i] + max(DP[i+1][p], DP[i+1][a]) DP[i][a] = a[i] + max(DP[i+1][p] + p[i+1], DP[i+1][a] + a[i+1]) かな…? */