Обсуждение @ 1115. Корабли @ Timus Online Judge

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?

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