[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Прашање за "Вино"  XML
Forum Index » Задачи од национални натпревари
Author Message
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Задача: http://mendo.mk/Task.do?id=57

После читајќи го ова, не разбирам зошто не е спомнато динамичко за решавање за задачава? Дали не е можно или е преспоро? Јас пробав ама добивам Runtime Error.

Eве псевдокод

Бидејќи money_spent и gained_value можат да стигнат до 32*30000000, користам vector<map<int, map<int, int>>> за dp за да има доволно меморија.
Ова ми дава WA на еден кејс и Runtime Error на повеќе.
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Бидеќи никој не ми одговори повеќе од еден ден, одлучив да поразмислам уште малку. Одговорот е дека цената и вредноста на вино е преголема.
petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

Ако имаме 5 елементи (пр вина) и вредности (пр цени) од 1, 2, 4, 8, 16, тогаш има 2^5 = 32 различни збирови.
1, 2, 1+2, 4, 1+4, 2+4, 1+2+4, 8, 1+8, ...
Со 32 вина, има премногу различни вредности. Да беа цените/вредностите помали, можеби ќе можеше вака.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team