PKUPKU

1. PKU 3176 Cow Bowling

32問。

PKU 3176 Cow Bowling

普通に上から全経路試すとO(2^N)なのである地点を終点とする経路のうち最高のスコアになるものをメモしておく。

一番上のものを終点とする経路のうち最高のスコアになるものはそれ自身なので自明で、二段目以降は一段上の左右両隣のうちスコアの大きい方を採用していく。計算量はO(N²)。