doxpox55's blog

By doxpox55, 4 years ago, In English

Hello, Good people. Hope you all are doing well. I am trying to solve the problem for a while but didnt come up any idea. Can anyone tell me how can I solve this problem?

Problem Link: https://vjudge.net/problem/UVA-1231

Thanks in advance. :)

  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Dynamic Programming! Suppose $$$T$$$ is the number of trees, $$$H$$$ is the height of each tree and $$$F$$$ is the parameter that is given in the input. At first let $$$tree[t][h]$$$ be the number of acorns on the tree $$$t$$$ at height $$$h$$$. Simply let $$$dp[t][h]$$$ be the maximum number of acorns the squirrel can collect if he is on the tree $$$t$$$ at height $$$h$$$. $$$dp[t][0] = 0$$$ for every $$$t$$$. Also let $$$best[h]$$$ be the maximum number of acorns he can collect, if he is at the height $$$h$$$ and he can freely choose any tree to descent from, in other words, $$$best[h]$$$ is the maximum of $$$dp[t][h]$$$ for all $$$t$$$. So the recurrence will be like this : $$$dp[t][h] = tree[t][h] + max(dp[t][h - 1], best[h - F])$$$. This means, the squirrel is either going to remain on the same tree and descent one meter, or is going to jump on another tree and lose $$$F$$$ meters in height, and we choose the maximum among those two cases. Note that $$$h - F$$$ could be negative so in that case it must be assumed zero. The answer to the problem is $$$best[H]$$$.

Implementation