HBC24588Min酱要旅行,背包问题,动态规划[USACO 2014 Mar S]The Lazy Cow题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance. The field Bessie inhabits is described by an N by N grid of square cells (1

It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance. The field Bessie inhabits is described by an N by N grid of square cells (1 <= N <= 400). The cell in row r and column c (1 <= r,c <= N) contains G(r,c) units of grass (0 <= G(r,c) <= 1000). From her initial square in the grid, Bessie is only willing to take up to K steps (0 <= K <= 2*N). Each step she takes moves her to a cell that is directly north, south, east, or west of her current location. For example, suppose the grid is as follows, where (B) describes Bessie's initial position (here, in row 3, column 3): 50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9 If K=2, then Bessie can only reach the locations marked with *s. Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location in the grid.

想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。

标签： HBC24588Min酱要旅行 背包问题 动态规划[USACO 2014 Mar S]The Lazy Cow题解