So I was goofing around and playing computer games during lock down 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?
↵
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?
