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. :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 162 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
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. :)
Название |
---|
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]$$$.