Blue Bridge Cup algorithm training boring funny Python 100 points

Typical knapsack problem , Use a two-dimensional matrix to record the state

n = int(input())
sticks = list(map(int, input().split()))
volumn = sum(sticks) // 2 + 1
# The volume of the backpack
res_map = [[-1 for _ in range(n + 1)] for _ in range(volumn)]
res_map[0][0] = 0

Index records with the first dimension “ The longest stick ” - “ Secondary bar ”, The second dimension index record “ Have considered before n A stick ”, Corresponding cell record “ The longest stick ” And “ Secondary bar ” Length of equal length part

The reason why the backpack volume is so set is ： To combine equal length rods , therefore “ The longest stick ” - “ Secondary bar ” <= sum(sticks) // 2

Every time the stick is taken into account , Can choose ：

1. Not with “ The longest stick ”、“ Secondary bar ” superposition
2. And “ The longest stick ” superposition
3. And “ Secondary bar ” superposition
4. And “ Secondary bar ” superposition ,“ Secondary bar ” Turn into “ The longest stick ”,“ The longest stick ” Turn into “ Secondary bar ”

for idx in range(1, n + 1):
# The first idx Add a stick to the consideration
for res in range(volumn):
stick = sticks[idx - 1]
res_map[res][idx] = res_map[res][idx - 1]
# Not with ” The longest stick ”、“ Secondary bar ” superposition , Direct transfer status
last_state = res - stick
# Find a state to pass
if last_state >= 0:
# Judge whether the status is legal
last_value = res_map[last_state][idx - 1]
if last_value >= 0:
res_map[res][idx] = last_value
# And “ The longest stick ” superposition , The equal length part does not change
last_state = res + stick
if last_state < volumn:
last_value = res_map[last_state][idx - 1]
if last_value >= 0:
res_map[res][idx] = max([res_map[res][idx], last_value + stick])
# And “ Secondary bar ” superposition , The isometric part changes ———— Compare and take the best
last_state = stick - res
if last_state >= 0:
last_value = res_map[last_state][idx - 1]
if last_value >= 0:
res_map[res][idx] = max([res_map[res][idx], last_value + stick - res])
# And “ Secondary bar ” superposition ,“ Secondary bar ” Turn into “ The longest stick ”,“ The longest stick ” Turn into “ Secondary bar ”, The isometric part changes ———— Compare and take the best 

The end result is “ The longest stick ” - “ Secondary bar ” = 0, And consider all the sticks , Corresponding res_map[0][-1],print come out

Full marks end