Author |
Message |
25/07/2018 11:28:04
|
VlatkoSh
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 на повеќе.
|
|
|
26/07/2018 16:54:46
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Бидеќи никој не ми одговори повеќе од еден ден, одлучив да поразмислам уште малку. Одговорот е дека цената и вредноста на вино е преголема.
|
|
|
27/07/2018 00:14:55
|
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 вина, има премногу различни вредности. Да беа цените/вредностите помали, можеби ќе можеше вака.
|
|
|
|
|
|