73A - The Elder Trolls IV: Oblivon
I think there exists a general method to solve any n-dimensional cases. Suppose that we are given n elements, and we denote them as a[0], a[1],.... At first, we calculate k/n (integer division) and k%n. Then, we find out every a[i] such that a[i]-1≤k/n, and denote the number of such elements as NUM. Furthwrmore, we update the following values:
k=k-(a[i]-1), a[i]=1, n=n-NUM
We repeat the above steps until at least one of the following conditions is satisfied:
n=0, i.e., no more a[i] can be cut.
k=0, i.e., we have no more chances to cut any a[i].
k/n=0, i.e., we only need to deal with the left k%n chances.
If k/n=0 but k%n>0, we can just find all the a[i] that satisfies a[i]>1, and update a[i]=a[i]-1 and k=k-1. This operation stops if either k=0 or no more such a[i] can be found.
This is a very "brain storm" problem. Although only m new scores are given, we can add n-m zeros to obtain a n-length sequence, denoted as S, which is further sorted in a decreasing order. We first try to find the worst rank.
It is obvious that to obtain the worst rank, the target racer should add the minimum value of S. Then, we sort all the racers in a decreasing order, and denote the current rank of target racer as R. For the racers with better rank than R, we should assign the minimum values of S to them, too. Thus, we use a pointer R2 to denote the rightmost position of S, which is still not assigned to any racer. We scan the racers with rank worse than R, and calculate whether it is possible to achieve a better rank if the score with index R2 is added. If yes, we move on to check next racer and update R2=R2-1. Otherwise, we only decrease R2 by one check again. During this process, we should record the number of racers which have better ranks than R, and this is just answer.
Now, we try to find the best rank. We give the target racer the highest score, and sort all the racers again in a decreasing order. For the racers who have better rank than R, we should assign the maximum scores to them, since they have already got better ranks even without any extra scores. We need to introduce another pointer R1 to denote the leftmost position of S which has not been assigned to any racer. Then, we scan the racers with worse ranks, and check whether it is possible to obtain a better rank than R if giving the score at R2. If yes, we in fact should give the score R1 rather than R2 to him, since "he is surely" to achieve a better rank, while updating R1++. If no, we should decrease R2 by one and check again. For this case, we should introduce a variable RES, which is used to denote the number of skipped R2. In fact, the previous opeartions under "YES" is not correct.... Instead, if yes, we should first check whether RES is larger than zero or not. If RES>0, we add R by one while decreasing RES by one; otherwise we update R1=R1+1, and also add the number of racers who have better ranks by one.
This is a standard DP problem. It suffices to use dp[n][z][k] to denote the maximum value under the state of "dealing with the n-th character in the given string, changing this letter to 'z', the number of changed letters being no larger than k". The updating formula is
1) z=s[n], dp[n][z][t]=max(all z', dp[n][z'][t]+weight[z'][z])
2) z!=s[n], dp[n][z][t]=max(all z', dp[n][z'][t-1]+weight[z'][z])
Comments (0)
