Author |
Message |
26/03/2015 11:00:38
|
despotovski01
Joined: 23/02/2014 14:36:12
Messages: 37
Offline
|
Здраво,
Имам прашање за задачата Палиндроми http://mendo.mk/Task.do?id=477
Успеав да најдам две "алчни" решенија, но не добивам точни одговори за сите случаи. Може само некој да ми помогне во која насока да размислувам за динамично решение?
Фала однапред
|
|
|
26/03/2015 13:01:33
|
addictus
Joined: 08/10/2010 11:22:51
Messages: 23
Location: Куманово
Offline
|
Greedy не поминува за оваа задача. За динамичко, може задачава да се претстави како варијација на knapsack проблемот, но со посебен услов (на бројот S не смееш да додадеш палиндром поголем или еднаков на S).
Станува збор за еднодимензионална низа каде:
DP [x] - најмал број на палиндроми што треба да се додадат на S за да го добиеш бројот x.
DP [S] = 0
За ова ќе ти е потребно претходно да ги имаш генерирано сите палиндроми од 2 до 99,999.
Сложеност : O(E * N) каде што E е бројот што треба да го добиеш а N е бројот на палиндроми што постојат (1,097 вкупно).
|
Решенија на задачи - aandevski.wordpress.com |
|
|
05/09/2015 00:01:46
|
filipdimitrovski
Joined: 04/09/2015 21:57:38
Messages: 2
Offline
|
@addictus
@despotovski
Не ми се јасни примерите кај „Палиндром“, како може ова да е најкраток пат од 7 до 53:
Според мене, ова е пократок:
EDIT:
нвм, требало секој палиндром да е помал од S, a не E.
This message was edited 1 time. Last update was at 05/09/2015 00:09:57
|
|
|
04/03/2019 19:35:17
|
MODDI
Joined: 27/12/2017 18:17:00
Messages: 39
Offline
|
Ја решавав задачава со Дијкстра, кодов ми вади 3 точни тест примери, 3 погрешни, а останатите Runtime Error, кај ми е грешката ја неможев да ја пронајдам
|
|
|
05/03/2019 20:47:48
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
MODDI wrote:Ја решавав задачава со Дијкстра, кодов ми вади 3 точни тест примери, 3 погрешни, а останатите Runtime Error, кај ми е грешката ја неможев да ја пронајдам
Кога користиме Dijkstra, сакаме да ги посетуваме темињата според растојание (најпрвин оние кои се најблиску до почетокот / најмалку операции на пример), па затоа и користиме priority_queue. Ти не ги споредуваш по растојание, па потоа чуваш повеќе решенија за до последниот број, итн.
Вака треба да се поправи (спореди го со твојот код, има само неколку промени).
|
|
|
|
|
|