HBC24855斐波那契序列,枚举,过关题目[USACO 2009 Nov B]Cow Pinball题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

The cows are playing that cool Japanese 'pinball' game called Pachinko. You've probably seen it, you drop a ball in the top and it hits nails on the way down, veering just a little left or right, until the ball comes out the bottom.This pachinko game is special: the ball always hits the top nail of the R rows of nails (1

The cows are playing that cool Japanese 'pinball' game called Pachinko. You've probably seen it, you drop a ball in the top and it hits nails on the way down, veering just a little left or right, until the ball comes out the bottom. This pachinko game is special: the ball always hits the top nail of the R rows of nails (1 <= R <= 25) and then will hit either the right or left nail underneath that. From there, the ball can hit the next nail that's just a bit lower and to the left or right of the second nail, and so on. The ball never veers too far (i.e., more than 1/2 nail away) from the nail it just hit. This game also has scoring that's unique: you get points X_{ij} X ij ​ (0 <= X_{ij} X ij ​ <= 3,000) for each little nail you hit on the way down. The cows want to maximize their score on this machine. What is the best score they can achieve? Here's an example triangle and a good route: 7 *7 3 8 *3 8 8 1 0 *8 1 0 2 7 4 4 2 *7 4 4 4 5 2 6 5 4 *5 2 6 5 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. It's not possible to go from 7 to 8 to 8 -- the 8 on the third row is too far away.

标签： HBC24855斐波那契序列 枚举 过关题目[USACO 2009 Nov B]Cow Pinball题解