ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1115. Корабли

How to solve this problem? Is it a NP problem?
Послано Saturn 5 июл 2004 15:22
How to solve this problem? Is it a NP problem?
Thanks
Re: How to solve this problem? Is it a NP problem?
Послано Saturn 5 июл 2004 23:54
I used full search and got TLE#5
Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!
Послано Yu YuanMing 7 июл 2004 09:22
I think the problem is NP (+)
Послано Dmitry 'Diman_YES' Kovalioff 7 июл 2004 17:31
It is one of knapsack-problem's variations, which is obviously NP. I used brute force with some optimizations and got AC within very short time. Of course, DP will work because of weak restrictions, but brute force is a classical way to solve this problem.

Edited by author 07.07.2004 17:33
Re: Read the problem carefully.You must be missing some important describe.By the way,DP+DFS will work...good luck!
Послано Saturn 8 июл 2004 00:08
Can you give me more details?