Kontrprzykład i podpowiedz

Question

Zadnaie jest takie ----->       http://main.edu.pl/pl/archive/oig/6/apt

Oto moj kod:

#include <iostream>

using namespace std;

int s,n;
int *t;
int *w;

int main()
{
    s=0;
    cin>>n;
    t=new int [n];
    w=new int [n];

    for(int i=0;i<n;i++)
    {
        cin>>t[i];
    }
    for(int i=n-1;i>=0;i--)
    {
        w[i]=t[n-1];
    }
     for(int i=n-2;i>=0;i--)
    {
        for(int j=i;j>=0;j--)
        {
            if(w[j]>t[i])w[j]=t[i];
        }
    }
    for(int i =0;i<n;i++)
    {
        s+=w[i];
    }
    cout<<s<<endl;
    return 0;
}

chodzi o to ze w tablicy w[i] zapisuje najnizsza wartosc jaka trzeba zaplacic za 1 miejsce w drodze do tego miejsca. i potem ide po kolei i sumuje te wartosci/ 

i tak dla np.   kolejki 5 2 4 3

zapisuje  w takie   2 2 3 3

bo na 1 moge sie dostac za 2 potem znow za 2 a potem za 3 i za 3 suma = 10 

ale niektorych testow mam "zla odpowiedz" a dla innych "program wywłaszczony".. prosze o kontrprzykad, opinie czy ten algorytm jest poprawny i odp. co to znaczy "program wywslaszcozny"?

dzieki za kazde odp.

Answer 1

Wydaje mi się, że Twoje: s może wyjść po za int'a przy zadanej wielkości danych... Może stąd to wywłaszczanie.

Comments

tak dzieki za odp masz racje