Zadaca triagolnik

Zdravo na site. Ja citav zadaca triagolnik
link-http://mendo.mk/algoritmi/Task.do?competition=150&id=103" target="_new" rel="nofollow"> http://mendo.mk/algoritmi/Task.do?competition=150&id=103
Imam ideja. i mislam deka e ok. Prasanjeto mi e nesto drugo.
Vsusnost imam 2 prasanja.
Pocetokot na kodot ( input ) ne funkcionira dobro. Jas koristam matrica vo slucajov i na pocetok ja polnam so nuli poradi idejata:
(Pocnuvam so matrica od nuli. I potoa gi vnesuvam site elementi vo matricata do (n-j) vo sekoja kolona , i n redici .
Na primer ako inputot izgleda vaka:
3
1 2 3
1 2
1
jas sakam matricata da izgleda vaka:
1 2 3
1 2 0
1 0 0
Potoa pocnuvam od mat[0][0] element vo matricata i e dvizam nadolu-nadesno-ili dijagonalno. vo zavisnost koj element e najmal.
Ili pocnuvam od najdolu i se dvizam nagore pravejki minimalni presmetki. )
1 Prasanje:
Koe e poefikasno resenie? Da pocnam od najdolu odejki nagore, ili od najgore pa da se dvizam nadolu?
2 Prasanje:
Kako da go popravam kodot za da ja dobijam posakuvanata matrica dadena pogore?
Kod:

Kodot e daden zaedno so cout for-ovite.
Fala odnapred

This message was edited 1 time. Last update was at 30/10/2018 17:34:17

Ok. Go resiv problemot
Compilerot ne rabotese dobro

Zdravo uste ednas. Go resiv problemot, no ispadna deka mi dava nadminat vremenski limit vo slucajot so baranjeto na odgovorot vo vtoriot red , indexite . Eve konecen kod:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int t=n;
    int mat[n+1][n+1];
    int input;
    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    t=n;
    memset(mat, 0, sizeof(mat));
    
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n-i; j++)
            {
                cin>>input;
                mat[i][j]=input;
                dp[i][j]=input;
                
                
            }
            
            
        }
    
    int MIN=10000;
    bool zero=false;
    for(int i=n; i>=0; i--)
    {
        for(int j=n; j>=0; j--)
        {
            zero=false;
            if(dp[i][j]==0)
            {
                continue;
            }
            else if(dp[i+1][j]==0 or dp[i][j+1]==0 )
            {
                continue;
            }
            else{
                
                
                    if(dp[i+1][j+1]==0)
                    {
                        zero=true;
                    }
                    
                    if(zero)
                    {
                        MIN=min(dp[i+1][j],dp[i][j+1]);
                        dp[i][j]+=MIN;
                    }
                    else
                    {
                        MIN=min(dp[i+1][j], min(dp[i][j+1],dp[i+1][j+1]));
                        dp[i][j]+=MIN;
                    }
                
            }
        }
    }
    cout<<dp[0][0]<<endl;
    int pos=dp[0][0];
    int i=0; 
    int j=0;
    
    while(dp[i+1][j]!=0 && dp[i][j+1]!=0)
    {
        if((dp[i][j+1]< dp[i+1][j] && dp[i][j+1]<dp[i+1][j+1]) && (dp[i][j+1]!=0))
        {
            pos=dp[i][j+1];
            j++;
        }
        else if((dp[i+1][j]< dp[i][j+1] && dp[i+1][j]<dp[i+1][j+1]) && (dp[i+1][j]!=0))
        {
            pos=dp[i+1][j];
            i++;
        }
        else if((dp[i+1][j+1] <dp[i+1][j] && dp[i+1][j+1]< dp[i][j+1] ) && (dp[i+1][j+1]!=0))
        {
            pos=dp[i+1][j];
            i++;
            j++;
        }
        
        if(dp[i+1][j]==0 || dp[i][j+1]==0)
        {
            cout<<i+1<<" "<<j+1<<endl;
            return 0;
        }
    }
    return 0;
}

BATIR wrote:Zdravo uste ednas. Go resiv problemot, no ispadna deka mi dava nadminat vremenski limit vo slucajot so baranjeto na odgovorot vo vtoriot red , indexite . Eve konecen kod:

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

Во последниот дел од кодот, само користи помало и еднакво наместо помало при споредбите, и немој да користиш нула (0) туку некој голем број за означување специјални случаи (инаку споредбите нема да ти функционираат).
Вака:

#include <bits/stdc++.h>
using namespace std;

int BIG_NUMBER = 1000000000;

int main()
{
    int n;
    cin>>n;
    int t=n;
    int mat[n+1][n+1];
    int input;
    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    t=n;
    memset(mat, 0, sizeof(mat));
    
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n-i; j++)
            {
                cin>>input;
                mat[i][j]=input;
                dp[i][j]=input;
                
                
            }
            
            
        }
    
    int MIN=10000;
    bool zero=false;
    for(int i=n; i>=0; i--)
    {
        for(int j=n; j>=0; j--)
        {
            zero=false;
            if(dp[i][j]==0)
            {
                continue;
            }
            else if(dp[i+1][j]==0 or dp[i][j+1]==0 )
            {
                continue;
            }
            else{
                
                
                    if(dp[i+1][j+1]==0)
                    {
                        zero=true;
                    }
                    
                    if(zero)
                    {
                        MIN=min(dp[i+1][j],dp[i][j+1]);
                        dp[i][j]+=MIN;
                    }
                    else
                    {
                        MIN=min(dp[i+1][j], min(dp[i][j+1],dp[i+1][j+1]));
                        dp[i][j]+=MIN;
                    }
                
            }
        }
    }
    cout<<dp[0][0]<<endl;
    int pos=dp[0][0];
    int i=0; 
    int j=0;
	
	for (int k=0; k<=n; k++)
	   for (int l=0; l<=n; l++)
	        if (dp[k][l] == 0) { dp[k][l] = BIG_NUMBER; }
    
    while(dp[i+1][j]!=BIG_NUMBER && dp[i][j+1]!=BIG_NUMBER)
    {
        if((dp[i][j+1]<= dp[i+1][j] && dp[i][j+1]<=dp[i+1][j+1]) && (dp[i][j+1]!=BIG_NUMBER))
        {
            pos=dp[i][j+1];
            j++;
        }
        else if((dp[i+1][j]<= dp[i][j+1] && dp[i+1][j]<=dp[i+1][j+1]) && (dp[i+1][j]!=BIG_NUMBER))
        {
            pos=dp[i+1][j];
            i++;
        }
        else if((dp[i+1][j+1] <=dp[i+1][j] && dp[i+1][j+1]<= dp[i][j+1] ) && (dp[i+1][j+1]!=BIG_NUMBER))
        {
            pos=dp[i+1][j];
            i++;
            j++;
        }
        
        if(dp[i+1][j]==BIG_NUMBER || dp[i][j+1]==BIG_NUMBER)
        {
            cout<<i+1<<" "<<j+1<<endl;
            return 0;
        }
    }
    return 0;
}

Fala. Za pomalo ednakvo ne mi tekna

No, zosto ne raboti so nuli?

BATIR wrote:Fala. Za pomalo ednakvo ne mi tekna No, zosto ne raboti so nuli?

Кажав, поради споредбите.

На пример, разгледај го ова:

Ти проверуваш дали е нула само (dp[i][j+1] != 0). Но што ако е нула (dp[i+1][j])? Тогаш dp[i][j+1] нема да биде помало од dp[i+1][j].

Можеш и со нули, ама доста покомплицирано

Fala uste ednas. Razbrav sega