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



Joined: 20/06/2015 16:36:50
Messages: 155
Offline

Spored mene , ovaa zadaa se resava so dp, samo ako nekoj znae moze da mi dae hint kako kje ide dinamickoto...
Fala odnapred
petarsor



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

BATIR wrote:Spored mene , ovaa zadaa se resava so dp, samo ako nekoj znae moze da mi dae hint kako kje ide dinamickoto...
Fala odnapred


1. Точно е, може да се реши со динамичко програмирање.
2. Не треба никакви дополнителни структури (дрва, незнам што), само динамичко програмирање (5-6 редови код)
3. Состојбата можеш да ја чуваш со две димензии dp[x][y].

Толку би помогнал јас
MODDI



Joined: 27/12/2017 18:17:00
Messages: 39
Offline

Задачава неможев да ја сфатам, поточно на врските немозам да го сфатам начинот на кој тие се добиваат, сликата што е дадена во текстот на задачата повеќе ме збунува мене отколку ми појаснова, ако може некој барем псевдо код да даде или base-cases од dpto и да ми ја појасни задачава.
petarsor



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

MODDI wrote:Задачава неможев да ја сфатам, поточно на врските немозам да го сфатам начинот на кој тие се добиваат, сликата што е дадена во текстот на задачата повеќе ме збунува мене отколку ми појаснова, ако може некој барем псевдо код да даде или base-cases од dpto и да ми ја појасни задачава.


Сликата одговара на примерот даден во текстот на задачата. Незнам што те збунува, имаш почетни врски (тоа се врски помеѓу соседните букви од почетниот стринг) и плус има 14 дополнителни врски (тоа се сите нацртани врски кои не се од почетниот стринг). Единствено може да те збуни ако броиш 13 такви врски, а излезот е 14 - тоа е веројатно бидејќи не ја гледаш врската што е помеѓу U и A (веднаш над почетокот). Какви дополнителни врски се можни е дадено во текстот на задачата - цитат: "Тоа значи дека се возможни врските A – U, U - A, C – G, G – C, G – U и U – G.".

Ако дадам повеќе информации за динамичкото, исто е како да сум го дал целото решение, така да еве:
MODDI



Joined: 27/12/2017 18:17:00
Messages: 39
Offline

Задачата Rectangles од делот интернационални е повторно дп, ми работи на 2/10 малку хелп.
petarsor



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

MODDI wrote:Задачата Rectangles од делот интернационални е повторно дп, ми работи на 2/10 малку хелп.


Ова е друга задача, не би требало да е во оваа тема.
Во секој случај, пробај направи си свои примери (или симни ги тие од МЕНДО) и види каде ти е грешката.

Еве, ти ја поправив задачата (код долу), ама најдобро е да не го гледаш тоа и да пробаш сам.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team