For convenience, let's define $$$k = \max(a, b, x, y)$$$, use operation 1 for "You will get a card with $$$a$$$ HP, and $$$b$$$ damage", operation 2 for "If you have at least one card, choose one of your cards and increase its HP by $$$x$$$" and operation 3 for "If you have at least one card, choose one of your cards and increase its damage by $$$y$$$", operation 4 for "You will get a prop with $$$w$$$ power", operation 5 for "You can choose at most one of your cards and multiply its damage by $$$10^9$$$", "the $$$i$$$-th card" for the card we get from vertex $$$i$$$ (It must be operation 1 on vertex $$$i$$$), "do operation 2/3/5 onto card $$$i$$$" for "When we do this operation 2/3/5, we will choose the card $$$i$$$ and increase his HP or damage".
Let us consider the problem without the operation 5, what's the maximum possible answer. If you want to maximize the the sum of the power of your cards, the answer will not exceeding $$$(100 \times 200)^2 = 4 \times 10^8$$$; If you you want to maximize the the sum of the power of your props, the answer will not exceeding $$$200 \times 10^6 = 2 \times 10^8$$$. Because $$$4 \times 10^8 + 2 \times 10^8 = 6 \times 10^8 < 10^9$$$, so the operation $$$n$$$ is the most important. Let's called the card we wil do the operation 5 onto it the "flash card". Let's use meet-in-the-middle, the problem is divided into two subproblems — the game before we get the flash card and the game after we get the flash card.
1. The game after we get the flash card
It's a easy problem, we can use dynamic programming to solve this problem.
Since the most important thing is the HP and damage of the flash card, so we define the following dynamic programming state:
- $$$dp_b(u, a)$$$ means we are current at vertex $$$u$$$, the current HP of the flash card is $$$a$$$, the maximum damage of the flash card.
- $$$dp_c(u, a)$$$ means we are current at vertex $$$u$$$, the current HP of the flash card is $$$a$$$, the damage of the flash card is $$$dp_b(u, a)$$$, the maximum sum of the power of all the other cards and props.
Since $$$a \leq nk$$$, the time complexity of the transition is $$$O(m \times n \times k)$$$.
2. The game before we get the flash card
This is the key of the problem, and since it's much more difficult, we first consider the subproblems of this problem.
I. If the graph is a chain, and all the operation 2 and operation 3 is after the operation 1
Lemma. We will do all the operation 2 onto one of the cards, symmetrically we will also do all the operation 3 onto one of the cards.
Proof. We consider a sequence of operations, let's consider if we do all the operation 1 on the card with the max damage after doing all the operation 2, the answer won't be worse, we can do all the operation 1 onto this card instead, then we make a symmetrical adjustment, the answer won't be worse, and all the operation 2 is done onto one of the cards, all the operation 3 is done onto one of the cards.
II. If the graph is a chain
It's similar to the subproblem I. If we say subproblem I is like a "global max value", then subproblem II is like a "prefix max value".
Let's define $$$p_i$$$ means we will do the operation 2/3 on vertex $$$i$$$ onto the $$$p_i$$$-th card.
Lemma1. If there is a operation 2 on vertex $$$i$$$ and a operation 2 on vertex $$$j$$$, if $$$p_i < j < i$$$, we will have $$$p_j = p_i$$$.
Proof. Let's consider the final HP and damage of the cards after all the operations. Because we do the operation 2 on vertex $$$i$$$ onto the $$$p_i$$$-th card, for all $$$i' < i$$$, the damage of the $$$i'$$$-th card is not larger than the $$$p_i$$$-th card. So for $$$j$$$, if we don't do the operation 2 on vertex j onto the $$$p_i$$$-th card, we can do it onto the $$$p_i$$$-th card instead, the answer won't be worse.
Symmetrically, Lemma1 is also correct for operation 3.
Now we can use dynamic programming to solve the problem, we define the following dynamic programming state:
- $$$f(u, a, b)$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations and we will do the next several operation 2 onto a card with $$$b$$$ damage after all the operations, and this two cards are not the same.
- $$$g(u, a, b)$$$ means we are current at vertex $$$u$$$, We will do the next several operation 2 and operation 3 onto a card currently having $$$a$$$ HP and $$$b$$$ damage.
The time complexity is $$$O(m \times n^2 \times k^2)$$$, but it's not enough.
Lemma2. If a card has $$$a$$$ HP and $$$b$$$ damage after all the operations and it's not the flash card, $$$\min(a, b) \leq k$$$.
Proof. If we use this card as the flash card instead of the last one, and do all the operations done onto the last flash card onto this card, the power of the flash card will be larger. So it won't exist in this half problem.
Now the time complexity becomes $$$O(m \times n \times k^2)$$$, it's still not enough.
Lemma3. Let's define $$$A$$$ as the maximum HP of all the cards except the flash card after all the operations, $$$B$$$ as the maximum damage of all the cards except the flash card after all the operations, $$$\min(A, B) \leq k$$$.
Proof. Let's assume that the $$$i$$$-th card has $$$A$$$ HP after all the operations, the $$$j$$$-th card has $$$B$$$ damage after all the operations and $$$A > k, B > k$$$. If $$$i = j$$$, it conflicts with Lemma 2; If $$$i < j$$$, because of the Lemma 2, the HP of the $$$j$$$-th card after all the operations won't exceed $$$k$$$, let's use $$$A'$$$ as the HP of the $$$j$$$-th card after all the operations, and $$$B > k$$$, so we have done some operation 3 onto the $$$j$$$-th card. But because $$$A > k \geq A'$$$, if we do these operations onto the $$$i$$$-th card, the answer will be better; If $$$i > j$$$, it's symmetric with $$$i < j$$$.
But we can make the dynamic programming state better:
$$$f(u, a, b)$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations and we will do the next several operation 2 onto a card with $$$b$$$ damage after all the operations, and this two cards are not the same.
$$$g_a(u, a, a')$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations, we will do the next several operation 2 onto a card and totally increase $$$a'$$$ HP in the next several operations to reach it's HP after all the operations.
$$$g_b(u, b, b')$$$ it's symmetric with $$$g_a$$$, just swap "HP" and "damage".
Let's define $$$A$$$ as the maximum HP of all the cards except the flash card after all the operations, $$$B$$$ as the maximum damage of all the cards except the flash card after all the operations. We will find the $$$a, a', b, b'$$$ in $$$f, g_a, g_b$$$ is $$$O(k)$$$ because if $$$A \leq k$$$, using $$$g_a$$$ we can get the right answer, if $$$B \leq k$$$, using $$$g_b$$$ we can get the right answer.
the time complexity of the transition is $$$O(m \times k^2)$$$.
The transition is very complex, you can see more details in my code : )
In my code, I use $$$g(u)$$$ to make the transition better. When $$$a'$$$ or $$$b'$$$ reaches $$$0$$$, we reaches the vertex $$$u$$$ and there is a operation 1 on vertex $$$u$$$, I don't enumerate the value of the next $$$a$$$ and $$$b$$$ while transiting. I transit it to $$$g(u)$$$ first, and enumerate the value of the next $$$a$$$ and $$$b$$$ together.
III. the problem itself
Since the path is a chain, and we use dynamic programming to solve the problem. There's no difference whether the graph is a chain.
Time complexity: $$$O(m(nk+k^2))$$$
Memory complexity: $$$O(n^2k+nk^2)$$$