RNK

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

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].

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

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

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

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

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

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int size;
    cin>>size;
    int side[size][size];
    for(int i=0;i<size;i++)
        for(int j=0;j<2;j++)
            cin>>side[i][j];
      
    int dp[size][2];
    dp[0][0]=side[0][0];
    dp[0][1]=side[0][1];
    for(int i=1;i<size;i++)
    {
        if(i%2!=0)
        {
            dp[i][1]=max(dp[i-1][1]+side[i][0]+abs(side[i][1]-side[i-1][0]),dp[i-1][1]+side[i][1]+abs(side[i][0]-side[i-1][0]));
            dp[i][0]=max(dp[i-1][0]+side[i][1]+abs(side[i-1][1]-side[i][0]),dp[i-1][0]+side[i][0]+abs(side[i][1]-side[i-1][1]));
        }
        else
        {
            dp[i][1]=max(dp[i-1][1]+side[i][1]+abs(side[i][0]-side[i-1][1]),dp[i-1][1]+side[i][0]+abs(side[i][1]-side[i-1][1]));
            dp[i][0]=max(dp[i-1][0]+side[i][1]+abs(side[i][0]-side[i-1][1]),dp[i-1][0]+side[i][0]+abs(side[i][1]-side[i-1][0]));
        }
    }
    cout<<max(dp[size-1][0]-1,dp[size-1][1]-1);
     
    return 0;
}

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

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

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