Обсуждение @ 1005. Куча камней @ Timus Online Judge

Who solve this problem with DP,

Послано ural_ghost 31 окт 2007 20:40

I have solved it with Dp in 0.015.
Is there anyone fast(DP)?

Re: Who solve this problem with DP,

Послано AlainDelon 8 дек 2007 15:00

I'd be more interested in your memory strategy. I don't think DP alg will differ much for the same problem

Re: Who solve this problem with DP,

Послано Skhan 9 дек 2007 10:42

Maybe the test data are so simple, and DP is able to accept.
But I don't think DP method is right.

Re: Who solve this problem with DP,

Послано KIRILL(ArcSTUpid coder:) 10 дек 2007 02:24

dp(bug task) and bruteforce (2^n) are both accepted

Re: Who solve this problem with DP,

Послано Madhav 12 июн 2008 01:16

for me it got accepted with brute force

Re: Who solve this problem with DP,

Послано gaston770 9 фев 2009 03:29

Time : 0.015 (I think its the minimal time) C++ using maps and vectors

Used DP

Want d code? gaston770@gmail.com

Less than 15 lines of the algorithm

Re: Who solve this problem with DP,

Послано yzthz 17 мар 2009 18:54

My solution cost monstrously 0.187s using DP...

Re: Who solve this problem with DP,

Послано ans_ 28 сен 2013 19:10

Легко решается с динамическим програмированием. Делишь сумму камней на 2 части, потом запускаешь рюкзак до суммы камней/2, ответом будет являться abs(sum-2*maxx), где sum - сумма камней, а maxx - макс. вес, который мы можем поместить в наш "рюкзак"

Обсуждение задачи 1005. Куча камней