I could not associate the explanation of Case 2: T = 2 with the max_span_cost method in the given code. Can anyone explain
why the second dimension of dp in the code only has two values of dp[i].first and dp[i].second, instead of j values?
why does the return value from the max_span_cost method depends on whether the size of span is even or odd?
why are there two if statements which depend on whether the number of cows from i to the end is even or odd?
In the explanation, it says “we only care about the parity of the number of unpaired cows”. But it seems to me that the code cares about the parity of the number of cows (not just unpaired) from i to the end.
It seems to me that the final code dramatically simplifies the DP explanation. Any more hints would be really appreciated! Thanks so much!
Since the parity of j determines whether we can transition from dp[ub[i]][j-1] to dp[i][j]. In other words, when j_1 and j_2 have the same parity, we can transition from dp[ub[i]][j_1-1] to dp[i][j_1] if and only if we can transition from dp[ub[i]][j_2-1] to dp[i][j_2].
because we need to be able to pair up all the cows besides those that we chose not to pair
I am still confused. In the official solution, it said that Let dp[i][j] be the maximum sum of values of unpaired cows if we only consider i to n cows in the current chain and there are j unpaired ones. I assume that it means there are j unpaired ones from i to n so far. Please let me know if my understanding is correct.
Then, what is the definition of dp[i] and dp[i] in the code? They must have a different meaning from dp[i][j].
Moreover, what is the relationship between j_1 and j_2 in your explanation? Why is the transition to dp[i][j_1] dependent on the transition to dp[i][j_2]?