|
|
|
|
|
|
|
| 1 Матус Даниил Дмитриевич, 05 января 2021 г. 20:33:20 |
| да минимальный по весу поток ток надо список делать смежности и все будет ок по времени 0.06 по памяти 1мб
|
|
|
|
|
| 2 Зубков Олег Владимирович, 05 сентября 2014 г. 16:35:13 |
Так как это все-таки учебный сайт для школьников, полезно отметить следующие два момента:
1. в тексте задачи нигде четко не сказано, обязательно ли нужно использовать все k доминошек, или можно, если при меньшем числе доминошек можно получить большее значение, положить не все k костей. Простой пример:
2 3 3
1 5 4
3 5 1
Если требовать уложить именно 3 доминошки, то ответ будет 32, а при помощи двух можно получить 35. Логично было бы предположить, учитывая предложение из условия "найдите наибольшую сумму, которую он может получить", что ответом на этот тест будет 35. Однако, правильный ответ - 32, и всем, кто будет сдавать эту задачу полезно это знать. Кроме того, в текст условия нужно внести информацию о том, что уложить нужно именно все k костей домино.
2. Тема задачи указана как ДП (подразумевается, скорее всего, ДП по профилю), однако уложиться в указанные ограничения при таком подходе весьма сложно и лучше все-таки переместить задачу в раздел "теория графов" (min-cost-flow).
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
