Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Quantbox 2022 Online Assessment Question: Monster fight

Правка en1, от luvcoding99, 2023-10-31 13:00:57

I need to fight N monsters whose energy is given by the array Arr[1:n]. I need to maximize my glory points which are defined as the net number of battles won. Initially, I have Energy E and 0 glory points. I must battle the monsters sequentially from left to right in a queue. I have the following 4 options: 1. If my current energy is greater than the monster's energy I can defeat it and lose energy equal to that of the monster's energy and gain a glory point. 2. I may choose not to compete with the monster. Then neither my energy nor my glory point changes. 3. I may delay my encounter with the monster by sending him to the back of the queue. Then neither my energy nor my glory point changes. 4. I may lose to the monster to gain its energy but lose a glory point. My energy should always be greater than 0. And glory points at all times greater than or equal to 0. Find the maximum value of glory points. Constraints: 1=<N<=1000 1<=E<=10^6 1<=Arr[i]<=10^6

Теги array, dynamic programming, queue

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский luvcoding99 2023-10-31 13:00:57 1030 Initial revision (published)