|
Модераторы: Alx, Fixin |
|
arcsupport |
|
|||
Опытный Профиль Группа: Участник Сообщений: 725 Регистрация: 24.10.2008 Репутация: нет Всего: 2 |
Постановка задачи:
1472. Марсианская армия Марсиане много веков назад перешли на использование в военных действиях огромных человекоподобных роботов. В ходе нынешней кампании по завоеванию Луны вся марсианская армия размещается в штабе на Марсе, при этом каждый военный управляет из штаба по интернету действиями своего робота. В марсианской армии поддерживается строгая иерархия — у каждого военного, кроме генерала (генерал в армии всего один), есть непосредственный командир. По марсианскому уставу разрешено только общение командира с непосредственным подчинённым. Такое общение происходит по локальной сети штаба. Каждый военный имеет в штабе собственный компьютер; компьютеры пронумерованы числами от 1 до N, где N — численность марсианской армии. С давних пор повелось, что компьютер подчинённого имеет номер строго больше компьютера командира. Военные, кроме номера компьютера, характеризуются своей надёжностью — действительным числом: владелец компьютера i имеет надёжность Ai. Все на Марсе знают, что надёжность генерала равна 1, а надёжность рядовых (рядовые и только они на Марсе не имеют подчинённых) равна 0. Наивно думать, что траффик внутри сети штаба ни во что не обходится военным. За каждый мегабайт траффика между i-м компьютером и компьютером командира владельца i-го компьютера главный марсианский провайдер требует плату в Ci золотых. Ситуацию осложняет то, что объём траффика между любой парой компьютеров в штабе является государственной тайной, и даже провайдеру он неизвестен. Провайдер поступает следующим образом: раз в месяц он присылает счёт, а военные сами вписывают в него траффик за месяц — неотрицательное число мегабайт. Пусть командир и подчинённый имеют компьютеры с номерами i и k соответственно. По договору с провайдером траффик по счёту между компьютерами i и k не должен быть меньше Ai–Ak. В начале нового месяца представителям провайдера известна иерархия чинов в марсианской армии и цены за мегабайт траффика, однако неизвестны Ai всех чинов, кроме генерала и рядовых, и уж, конечно, неизвестны заранее те суммы в мегабайтах, которые военные впишут в счёт. Хотелось бы знать, какое гарантированное количество золотых может получить провайдер. Исходные данные В первой строке записано целое число 2 ≤ N ≤ 100000 — численность армии. В следующих N–1 строках расположены пары целых чисел Ki, Ci — номер компьютера командира владельца i-го компьютера и стоимость мегабайта траффика между компьютерами i и Ki. 1 ≤ Ki < i ≤ N, 0 ≤ Ci ≤ 1000. Результат Выведите действительное число — минимальную сумму в золотых, которую может гарантировать себе провайдер. Число должно содержать ровно 2 знака после десятичной точки. Что делать? Это сообщение отредактировал(а) arcsupport - 6.1.2012, 09:47 |
|||
|
||||
Silent |
|
|||
Опытный Профиль Группа: Участник Сообщений: 252 Регистрация: 3.10.2006 Репутация: 1 Всего: 9 |
use DP, Luke!
у нас есть дерево, нужно найти максимальное значение Ai-Ak между узлами, например, динамическим программированием |
|||
|
||||
arcsupport |
|
|||
Опытный Профиль Группа: Участник Сообщений: 725 Регистрация: 24.10.2008 Репутация: нет Всего: 2 |
Silent, не могли бы Вы поподробнее объяснить
|
|||
|
||||
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |