If the given string contains the required characters except for '+', the answer is yes.
We can construct the binary sequence according to the requirement, and then calculate its value in decimal form.
Inverse the binary form and then compute the value...
This is in fact a straightforward implementation problem, but we should complete some pre-processing in order to avoid TLE.
The main issue that might lead to TLE is that we have to move to one of the four corners within one group. One group may consist of many squares with the same color, and according to DP and CP pointers, after we enter such a group, we must first determine the corner and then move to the next square (or group). This sub-problem can be solved based on DP algorithm. For instance, we use dp[0][i][j] to denote that if we are in the i-th row and j-column and facing to the right, then we should move to position dp[0][i][j], which assembles the prefix or suffix idea. Similarly, we implement the same pre-processing for the other three directions.
This problem can be solved by adopting a three dimensional DP. We use dp[i][j][0] and dp[i][j][1] to denote the maximum distance that we can reach, under the state that we have completed the first i commands, and implememted j changes, while facing to the right and left, respectively. For dp[i][j][0], it can transfer to states dp[i + 1][j + nextj][0] and dp[i + 1][j + nextj][1], where nextj ≥ 0 and j + nextj ≤ n. The detailed formula of dp[i][j][0] can be represented as follows, while dp[i][j][1] can be derived in a similar manner.
1) the i + 1-th command is 'F' and nextj is an even number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][0] + 1)
2) the i + 1-th command is 'T' and nextj is an odd number: the same as 1)
3) the i + 1-th command is 'F' ans nextj is an odd number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][1])
4) the i + 1-th command is 'T' and nextj is an odd number: the same as 3)
However, it is still not done here, since the maximum distance may be “negative”. In other words, we can achieve the maximum distance by moving to the left. Thus, we should implement DP again, but replace max with min. After all of the above steps, we will finally obtain the answer.
132D - Constants in the language of Shakespeare
Well, I searched on the Internet and found that it can be solved with a greedy algorithm. Nevertheless, I did not figure out how to prove it...
We start from the right bit and move to left. We will always try to find a subsequence consisting of consecutive 1s. If there is only one 1, we should assign a + 2^ to this position; otherwise, we should assign a - 2^ instead, while deleting these consecutive 1s but changing the next 0 into 1, which indicates that we add a + 2^ to that position, temporarily.
We give s=10011011 as a simple example. We scan from right to left and first find 11. Then, we assign - 20 and modify it as s=10011100, and find 111. Now, we assign - 22, and change it into s=10100000. Next, we assign + 25 and + 27. As a result, we obtain - 20 - 22 + 25 + 27.
Comments (0)
