/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 33ms 21.324 MiB

Code

from bisect import bisect_left

# Define constants
INF = 10**9
VOWELS = "aeiouaeiou"

def solve():
    # Read input
    n = int(input())
    s1 = "#" + input()  # Make the string 1-based indexing
    
    # Map vowels to indices
    mp = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
    
    # Precompute positions of each vowel in VOWELS
    pos = [[] for _ in range(5)]
    for i in range(len(VOWELS)):
        pos[mp[VOWELS[i]]].append(i)

    # Function to calculate the cost of moving from 'from' to 'to'
    def cost(from_vowel, to_vowel):
        # Using binary search to find the position
        return pos[to_vowel][bisect_left(pos[to_vowel], pos[from_vowel][0])] - pos[from_vowel][0]

    # DP memoization table
    dp = [[[-1 for _ in range(n + 1)] for _ in range(33)] for _ in range(6)]

    # Recursive function with memoization
    def rec(i, back, vis):
        if i > n: 
            return 0
        if dp[back][vis][i] != -1: 
            return dp[back][vis][i]
        
        ans = INF
        # Case when we continue with the same vowel as the previous one
        if back != 5:
            ans = cost(mp[s1[i]], back) + rec(i + 1, back, vis)

        # Try all unvisited vowels
        for ch in range(5):
            if (vis >> ch) & 1:  # If vowel 'ch' is already visited, skip it
                continue
            # Mark vowel 'ch' as visited
            ans = min(ans, cost(mp[s1[i]], ch) + rec(i + 1, ch, vis | (1 << ch)))
        
        dp[back][vis][i] = ans
        return ans
    
    # Call the recursive function starting with index 1, no previous vowel (back = 5), and no vowels visited
    print(rec(1, 5, 0))

# Main function to handle multiple test cases
if __name__ == "__main__":
    tc = int(input())
    for t in range(tc):
        solve()

Information

Submit By
Type
Pretest
Problem
P1140 Vowel arrangement
Language
PyPy 3 (Python 3.9.18 PyPy 7.3.15)
Submit At
2024-11-27 21:04:17
Judged At
2024-11-28 23:35:29
Judged By
Score
10
Total Time
33ms
Peak Memory
21.324 MiB