@Alisia

Ребят, помогите пожалуйста сделать задачку на динамику. Некоторые сделала, а эта не получается( Спасибо, тем кто откликнется огромное!

Найти стоимость самой дешевой правильной скобочной последовательности длины n. Стоимость последовательности определяется как сумма значений для каждой позиции от 1 до n. Если в i-ой позиции стоит открывающая скобка, то соответствующая стоимость равна O[i], а если закрывающая, то C[i].

Ввод
В первой строке содержится четное натуральное число n (2<=n<=100). В следующих n строках даны по два целых числа O[i] и С[i] (1<=O[i],C[i]<=1000) - соответственно стоимости открывающей и закрывающей скобок в i-й позиции.

Вывод
Выведите искомую минимальную стоимость.

Пример

Ввод
6
12 1
55 38
40 34
23 26
42 22
27 3

Вывод
138
P.S Пояснение
Искомая скобочная последовательность: ()(())

@Montanaa

Правильная скобочная последовательность это какая? Где у каждой скобки есть противоположная? Открывающаяся или закрывающаяся

accept

нет, ([)] - неправильная

@Net_Wanderer

алгоритмом "где дешевле там и берем" здесь не обойтись, беря открывающую скобку мы обязуем себя когда-то потом взять закрывающую



на втором шаге мы возьмем открывающую скобку, которая стоит 2 против 8 закрывающей, но при этом мы обязуем себя взять две последние закрывающие, независимо от их стоимости, потому как последовательность должна быть правильная (()), и получим результат 110 вместо 20

надо считать все возможные варианты, и тогда задача сводится к генерированию всех правильных скобочных последовательностей из n/2 пар, все остальное тривиально