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. :)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
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. :)
Name |
---|
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]$$$.