Enumerate all the feasible values of a and b.
The target integers must satisfy the following two conditions: the last digit is zero, and the sum of digits must be a multiple of three.
Therefore, there must exist at least one digit 0. Then, we calculate the sum of all the integers and the remainder after divided by three. If the sum is a multiple of three (remainder is zero), then all the digits should be output in a decreasing order. If the remainder is one, then we try to eliminate one single minimum digit that has the same remainder, i.e., 1, 4, 7, if there is no 1, 4, 7, then we try to eliminate two minimum digit that also has remainder two, i.e., 2, 5, 8. Note that at least one of the above two cases holds, since otherwise we can not have “the remainder of the sum is one after divided by three”. We deal with the case where the remainder is two in a similar manner.
The main idea is a greedy algorithm. We can divide the “optimal answer” into three cases according to which computer we select to first start with. Thus, we try to start with each of the three computers and the optimal answer must be included.
For each trial, the following work resembles the topological sorting. We keep completing jobs at the current computer until no jobs are remained, and then move to the next computer in the order of 1 → 2 → 3 → 1 → 2... as the first choice, and if this is infeasible, we move like 3 → 2 → 1 → 3 → 2....
I learned from the tutorials, and the main idea is to use dp[len][d] to denote the number of ways that we can build an integer with length len and digits d, d + 1, ..., 9. One can check the recursive formula shown there, which is quite clear and intuitive.
Notice that the original problem is equivalent to the following descriptions: we start from the left upper cell and select two paths to move to the right bottom cell, while achieving the maximum points. In other words, we can imagine that there are two players starting at the left upper cell and moving to the right bottom cell at the same time.
If we denote the current positions of player 1 and player 2 as (x1, y1) and (x2, y2), then after one step, player 1 will be either (x1 + 1, y1) or (x1, y1 + 1). Note that no matter which case occurs, the sum is always x1 + y1 + 1, and for player 2, we have similar observations. Therefore, we can use dp idea and denote the state by using a tuple (d, x, y), i.e., we use dp[d][x][y] to denote the maximum points that we can obtain, under the state that both two players are at the d-th second diagonal, while player 1 is at the x-th cell and player 2 is at the y-th cell of the current second diagonal, respectively. The recursive formula is straightfoward, but be careful that it is slightly different between d ≤ n and d > n.
Comments (0)
