Blue Bridge Cup [11th finals] tour arrangement Python 60 points

Although I didn't get a good score on this question , But because of thinking for a long time , So I still want to record

This problem is actually to find the longest increasing sequence , The length can be calculated with the normal dynamic programming idea , But also record the sequence 、 Find the least lexicographic order , This is a bit stingy

First deal with the input , With this regular expression you can match “Lan”、“Qiao”、“B” This string , use findall Function to find all such strings to complete the grouping

import re
mode = re.compile(r"[A-Z][a-z]*")
origin = re.findall(mode, input())
# Cut a string into several elements
length = len(origin)

Then use one n That's ok 2 Column matrix to record the status , The first 1 List front n The longest row increments the length of the sequence , The first 2 List front n Row longest increment sequence ( Dictionary order is the smallest )

dp = [[1, origin[_]] for _ in range(length)]
# initialization : Initial length of each position 1, The initial string has only the corresponding position element
for idx in range(1, length):
state, string = dp[idx]
# Read the current state
cur_ele = origin[idx]
# Read the elements under the current index
for last in range(idx):
l_state, l_string = dp[last]
# Read pre status
l_ele = origin[last]
# Read the element corresponding to the corresponding pre state index
if l_ele < cur_ele:
# < Operator comparison dictionary order , The incremental condition is satisfied
if l_state + 1 > state:
# l_string + cur_ele The length of the element > string The length of the element
state = l_state + 1
string = l_string + cur_ele
# Start state transition
elif l_state + 1 == state:
# l_string + cur_ele The length of the element == string The length of the element
string = min([l_string + cur_ele, string])
# Take the string with the smallest dictionary order
dp[idx] = [state, string]
# It was recorded that dp Matrix 

Then it is good to strictly control the minimum lexicographic order during the state transition

Consider that there may be more than one sequence that reaches the maximum length , So we have to ：

1. Find the maximum length
2. Find the sequence corresponding to the length
3. Take the output with the smallest dictionary order

result = max(dp, key=lambda x: x[0])[0]
# Find the longest length of the element
choose = []
for val, string in dp:
if val == result:
# Because there are multiple elements that reach the maximum length , So it needs to be summarized 、 Take the least lexicographic order
choose.append(string)
print(min(choose))

The final score 60, Everything else is “ Run timeout ”