A gaming algorithmic problem

Правка en2, от LilyWhite, 2020-06-08 09:54:40

So I was goofing around and playing computer games during lockdown and I've came across this problem.

Imagine I am playing a text-adventure game that has $$$n$$$ stories, by going through a story I gain $$$s_i$$$ points. After a story ends, I will face some choices, each choice are marked with a score range $$$[l_i, r_i]$$$ and I can only choose it if my current score is within the range. The choices will then lead me to another story.

I am standing at the beginning which is also a story, call it story $$$0$$$, the game ends when I reach the end of one story and cannot find a choice that is open for me (i.e my score is fit for the range limit).

Question: What's the maximum score I can get given that I know the structure of the game (how the choices are placed and their requirement, and the score increases for the stories) and I play optimally?

Is this question solvable within polynomial time?

Теги complexity, coronavirus

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский LilyWhite 2020-06-08 09:54:40 1 Tiny change: 'uring lock down and I' -> 'uring lockdown and I'
en1 Английский LilyWhite 2020-06-07 12:14:09 934 Initial revision (published)