We scan the sequence from left to right, and count the number of consecutive 'C's and 'P's. For each such subsequence of length m, it contributes m / 5 + (m%5! = 0) to the final answer.
We adopt a hash table to record the integers that have been appearing in the sequence. Then, the answer is just the number of integers that are not stored in the hash table.
We sort the events in an increasing order of their beginning time. Then, we scan the events from the last one to the first one, and for each one we check whether it can be completely covered by any other event. We denote the ending time of the i-th event in the sorted sequence as a[i]. It is obvious that only the first i - 1 events can completely cover it, and thus it suffices to check whether there is such an index j < i that a[j] > a[i]. Equivalently, we can check maxj = 0, 1, ..., i - 1a[j] > a[i]. Therefore, we adopt a prefix array to record the maximum a[m] for j = 1, 2, ..., m, and problem is solved.
A DP problem. At first, we use p[i][j] to denote the minimum number of changes we need to convert the substring starting from i while ending at j, to a palindrome, which can be computed with complexity O(n2).
Next, we consider how to describe the rules of dividing the original string into shorter ones with '+', since this helps determine the recursive formula of DP. Suppose that we are going to add m '+'s, and these '+' are always added from left to right. For instance, given that 'abcdefg' has been divided into 'ab'+'cdefg', if we will add another '+', then it can only added among 'cdefg' but 'ab' can not be divided any more. It can be shown that with this rule, the original string can always be divided into any shorter ones and thus no potential answer will be missed.
Now, we use dp[i][j] to denote that we have added i '+'s and the i-th '+' is at position j, and the minimum number to convert these substrings (the ones before j) into palindrome ones is dp[i][j].
Then, for state dp[i][j], it can transfer to states dp[i + 1][j + nextj], where j + nextj > j and j + nextj ≤ n, and dp[i + 1][j + nextj] = min(dp[i + 1][j + nextj], dp[i][j] + p[j + 1][j + nextj]). Also, we should record the “paths” so that we can trace back the division pattern.
The main idea is that for each position i, we calculate the longest substring that satisifes the requirement. We use p[i] to denote the total number of vowels in the first i positions.
At first, for any substring of length len, we transfer v ≤ 2c into 3v ≤ 2len. Then, for any position i, we should find out the maximum index j ≥ i so that 3(p[j] - p[i - 1]) ≤ 2(j - (i - 1)), which is equivalent to 3p[j] - 2j ≤ 3p[i - 1] - 2(i - 1). Therefore, we could build a segment tree based on 3p[j] - 2j. For any node in the tree, it stores the minimum value of its two child nodes (like a minimum heap). Then, for each i, the maximum j can be computed with complexity O(logN), by traversal from top to bottom (it is also possible that no j exists). Finally, we only need scan all the positions and find the maximum length.
Comments (0)
