Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
|
|
#1 | |
Cкобочки - C++13.11.2011, 21:26. Просмотров 546. Ответов 3
Метки нет Все метки)
(
Ребят, помогите пожалуйста сделать задачку на динамику. Некоторые сделала, а эта не получается( Спасибо, тем кто откликнется огромное!
Найти стоимость самой дешевой правильной скобочной последовательности длины 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 Пояснение Искомая скобочная последовательность: ()(())
0
|
|
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
|
|
13.11.2011, 21:29 | #2 |
Правильная скобочная последовательность это какая? Где у каждой скобки есть противоположная? Открывающаяся или закрывающаяся
0
|
accept
4829 / 3250 / 165
Регистрация: 10.12.2008
Сообщений: 10,569
|
|
14.11.2011, 06:42 | #3 |
нет, ([)] - неправильная
0
|
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
|
|
15.11.2011, 01:00 | #4 |
алгоритмом "где дешевле там и берем" здесь не обойтись, беря открывающую скобку мы обязуем себя когда-то потом взять закрывающую
например
( )
1 0 2 8 4 100 2 7 на втором шаге мы возьмем открывающую скобку, которая стоит 2 против 8 закрывающей, но при этом мы обязуем себя взять две последние закрывающие, независимо от их стоимости, потому как последовательность должна быть правильная (()), и получим результат 110 вместо 20 надо считать все возможные варианты, и тогда задача сводится к генерированию всех правильных скобочных последовательностей из n/2 пар, все остальное тривиально
0
|
15.11.2011, 01:00 | |