The solution is straightforward. We iterate between a and b to compute the GCD with n. Then, we decrease n with the corresponding value until n is reduced to zero, which also determines the winner.
We keep calculating the average points of each provided combination, and updating the maximum and minimum values. Then, for the left theorems, we check whether we can still select some of them to form a new eaxm (perhaps this is the main tricky issue). If yes, we update the maximum and minimum values again.
We use dp[n][m][w] to denote the maximum total value, under the condition that the n-th day is assigned with the m-th task while the the m-th task has points node[m].a + w. We use node[i] as a struct that has node[i].a, node[i].b and node[i].c as its elements, which have the same meanings as the problem mentions.
The updating of dp[n][m][w] is a little different from what I have known before. For instance, to compute some dp function f[n], we usually deduce its relationship with f[i] for i < n, and update f[n] from small indices to large indices. Once we “visit” f[n] for the first time, its value is determined, and will never be changed.
However, for this dp function, we start from some dp[n][m][w] and visit next potential states, perhaps with several times, and keep updating their values until they will never be visited any more. Specifically, from dp[n][m][w], we can move to dp[n + 1][m + i][w'], which means that for the n + 1-th day, we can select any one of the m + i-th task (i > 0) that have points node[m + i].a + w'. Note that some of the states perhaps can not be reached, since it requires that the next point xi must be either xi + 1 + k or xi + 1 × k, while xi should also be included in the given interval.
Generally speaking, from each determined state, we move to its next potential states and keep updating their values. At the same time, we record the transition between every two neighboring states.
Comments (0)
