Форум программистов, компьютерный форум CyberForum.ru

Cкобочки - C++

Восстановить пароль Регистрация
 
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
13.11.2011, 21:26     Cкобочки #1
Ребят, помогите пожалуйста сделать задачку на динамику. Некоторые сделала, а эта не получается( Спасибо, тем кто откликнется огромное!

Найти стоимость самой дешевой правильной скобочной последовательности длины 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
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
13.11.2011, 21:29     Cкобочки #2
Правильная скобочная последовательность это какая? Где у каждой скобки есть противоположная? Открывающаяся или закрывающаяся
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
14.11.2011, 06:42     Cкобочки #3
нет, ([)] - неправильная
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
15.11.2011, 01:00     Cкобочки #4
алгоритмом "где дешевле там и берем" здесь не обойтись, беря открывающую скобку мы обязуем себя когда-то потом взять закрывающую

например
( )
1 0
2 8
4 100
2 7


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

надо считать все возможные варианты, и тогда задача сводится к генерированию всех правильных скобочных последовательностей из n/2 пар, все остальное тривиально
Yandex
Объявления
15.11.2011, 01:00     Cкобочки
Ответ Создать тему
Опции темы

Текущее время: 20:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru