Zadaca boenje

Zdravo, ja resavam zadaca Boenje:
http://mendo.mk/Task.do?id=128
mi dava gresen rezultat , ne sum sigurna zosto, moze mal sovet ili ideja kako da go popravam kodot:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n],b[n],c[n];

for(int i=0; i<n; i++)
    {
        cin>>a[i];
        cin>>b[i];
        cin>>c[i];
    }

int result,minimum;
    int curr,prev=0;
    result=0;

for(int i=0; i<n; i++)
    {

prev=curr;
        //cout<<prev<<endl;
        minimum=min(a[i],min(b[i],c[i]));
        if (i==0)
        {
            result+=minimum;
            if(minimum==a[i])curr=1;
            else if(minimum=b[i])curr=2;
            else curr=3;
            continue;
        }
        else {
        if(minimum==a[i])
        {

if(curr==prev&&!(i==0))
            {
                int maximum=max(b[i],c[i]);
                if(maximum==b[i])
                {
                    curr=3;
                    result+=c[i];
                    //cout<<curr<<endl;
                }
                else if(maximum==c[i])
                {
                    curr=2;
                    result+=b[i];
                    //cout<<curr<<endl;
                }
            }
            else
            {
                curr=1;
                result+=a[i];
                //cout<<curr<<endl;
            }

}
        else if(minimum==b[i])
        {

if(curr==prev&&i!=0)
            {
                int maximum=max(a[i],c[i]);
                if(maximum==a[i])
                {
                    curr=3;
                    result+=c[i];

//cout<<curr<<endl;
                }
                else if(maximum==c[i])
            {

curr=1;
                    result+=a[i];
                    //cout<<curr<<endl;
                }
            }
            else
            {
                curr=2;
                result+=b[i];
                //cout<<curr<<endl;
            }

}
        else if(minimum==c[i])
        {
            if(curr==prev&&i!=0)
            {
                int maximum=max(a[i],b[i]);
                if(maximum==a[i])
                {
                    curr=2;
                    result+=b[i];
                    //cout<<curr<<endl;
                }
                else if(maximum==b[i])
                {
                    curr=1;
                    result+=a[i];
                    //cout<<curr<<endl;
                }
            }
            else
            {
                curr=3;
                result+=c[i];
                //cout<<curr<<endl;
            }
        }

}
    }
    cout<<result<<endl;
    return 0;
}

[code]
Fala odnapred

BATIR wrote:Zdravo, ja resavam zadaca Boenje:
http://mendo.mk/Task.do?id=128
mi dava gresen rezultat , ne sum sigurna zosto, moze mal sovet ili ideja kako da go popravam kodot:

Може да напишеме решение со динамичко програмирање (види решение подолу), или со рекурзија (бидејќи ако знаеме каква боја е претходниот прозорец, имаме само две опции за следниот, па сложеноста ќе биде 2^N).
Притоа, веројатно е полесно (бидејќи знаеме дека има три бои) да се размислува на начин што ќе извршиме некој алгоритам три пати (еднаш ќе поставиме првиот прозор да е една боја, па вториот пат некоја друга боја, итн), бидејќи тогаш лесно знаеме кои две бои може да е последниот прозор.

#include <iostream>
using namespace std;
 
int main()
{
    int n, i, j, result, current;
    int price[50][3];
    int dp[50][3];
  
    cin >> n;
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
  
    for(i=1; i<=n; i++)
    {
        for(j=0; j<3; j++)
            cin >> price[i][j];
    }
      
    dp[1][0] = price[1][0];
    dp[1][1] = dp[1][2] = 1000000000;
  
    for(i=2; i<=n; i++)
    {
        for(j=0; j<3; j++)
        {
            dp[i][j] = price[i][j]+min(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]);
        }
    }
  
    current = min(dp[n][1], dp[n][2]);
    result = current;
      
    dp[1][1] = price[1][1];
    dp[1][0] = dp[1][2] = 1000000000;
  
    for(i=2; i<=n; i++)
    {
        for(j=0; j<3; j++)
        {
            dp[i][j] = price[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]);
        }
    }
  
    current = min(dp[n][0], dp[n][2]);
    result = min(current, result);
      
    dp[1][2] = price[1][2];
    dp[1][0] = dp[1][1] = 1000000000;
  
    for(i=2; i<=n; i++)
    {
        for(j=0; j<3; j++)
        {
            dp[i][j] = price[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]);
        }
    }
  
    current = min(dp[n][0], dp[n][1]);
    result = min(current, result);
      
    cout << result << endl;
    return 0;
}

Исто, можеш да побараш, мислам дека има уште една тема на форумов за задачава.

Fala mnogu, vo megjuvreme moze primer za zadaci od DFS. Nekoi poednostavni, da vezbam

BATIR wrote:Fala mnogu, vo megjuvreme moze primer za zadaci od DFS. Nekoi poednostavni, da vezbam

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

Сепак, можеш лесно да најдеш задачи на интернет, на пример: http://www.spoj.com/problems/tag/dfs или http://codeforces.com/problemset/tags/dfs%20and%20similar?order=BY_SOLVED_DESC

Колку што видов набрзина, овие задачи ги дава како полесни, па можеш да пробаш да ги решиш:
http://www.spoj.com/problems/PT07Y/
http://www.spoj.com/problems/PT07Z/
http://www.spoj.com/problems/LABYR1/

Инаку, не сум голем фан на решавањето на задачи кога се знае алгоритамот, бидејќи мислам дека најтешкото нешто при решавање е да погодиш од кој тип е една задача, која податочна структура да се искористи и слично.
Имплементацијата (да се напише решението во C++) е полесно, барем кога зборуваме за задачи што се паѓаат на натпревари. По мене.

Fala mnogu! Ova mi znaci.

This message was edited 1 time. Last update was at 23/12/2017 19:44:15

И јас се согласувам со тоа , но еве ние почетниците уште ги учиме алгоритмите и дата структурите , па затоа ни би било олеснето ако унапред знаеме со што треба/можеме да решаваме.За да извежбаме убаво. Кога веќе алгоритмот ќе ни биде екстра разбран и извежбан тогаш веќе е друго. Но еве иако знам алгоритми и задачата кажува како може да се решава јас сепак не знам како да дојдам до тоа решение ..

This message was edited 1 time. Last update was at 11/01/2018 00:25:59

MOI wrote:
Може да напишеме решение со динамичко програмирање (види решение подолу), или со рекурзија (бидејќи ако знаеме каква боја е претходниот прозорец, имаме само две опции за следниот, па сложеноста ќе биде 2^N).
Притоа, веројатно е полесно (бидејќи знаеме дека има три бои) да се размислува на начин што ќе извршиме некој алгоритам три пати (еднаш ќе поставиме првиот прозор да е една боја, па вториот пат некоја друга боја, итн), бидејќи тогаш лесно знаеме кои две бои може да е последниот прозор.

Исто, можеш да побараш, мислам дека има уште една тема на форумов за задачава.

Значи сложеноста на алгоритамот многу би се намалила доколку имавме варијација кога последниот прозорец НЕ би бил "соседен" со првиот.

За 3 бои сложеноста би била околу O(9*n) или O(n*m) ако m е број на бои.