Zadanie algorytmiczne - złożoność obliczeniowa

Witam!
Mam do zrobienia takie zadanko:
http://main.edu.pl/user.phtml?op=showtask&task=kup&con=OIG4

Nie mam pojęcia, jak to jednak zrobić. Jedyne rozwiązanie, które przychodzi mi do głowy to totalny brute force i ma złożoność O(n^3-n). Czy ktoś mógłby podsunąć mi pomysł na prawidłowe i szybkie rozwiązanie zadania?

Pozdrawiam i z góry dziękuję
zaiks

Nie wiem jak tu znalazłeś O(n^{3). Najbardziej naiwne rozwiązanie ma O(n}2) -> dla każdego miasta wyliczasz sobie gdzie byłoby najkorzystniej sprzedać gdybyśmy kupili w tym mieście (czyli dla każego z n miast sprawdzamy n-1 możliwości). Można to przyspieszyć prawie 2 razy jeśli jednocześnie będziemy liczyć sobie w obie strony (tzn gdybyśmy kupowali i sprzedawali w danym mieście) ale to nadal O(n^2).

To nie jest najlepsze rozwiązanie, ale lepsze od najgorszego. ;)

Można obliczyć odległość między każdym z miast. Dla n miast wymagać to będzie 1+2+...+(n-1) operacji:

Przykładowo gdy mamy miasta: A, B, C, D, istnieją ścieżki:

A - B, A - C, A - D,
B - C, B - D,
C - D

Później dla każdej ścieżki obliczyć opłacalność (1+2+...+(n-1)+n operacji): |cena1-cena2|-koszt ścieżki = opłacalność (sprawdzamy też opłacalność dla ścieżek A-A, B-B, ..., gdzie koszt ścieżki wynosi 0)

Na koniec wybierać największą opłacalności (1+2+...+(n-1) operacji).

Zaczynamy w mieście o niższej cenie (1 operacja - porównanie cena1 i cena2).

Zrobiłem chyba tak jak powinno być i dostaję przekroczenie czasu wykonania ;/:

 #include <iostream>
#include <cmath>

using namespace std;

int miasta[1000000];
int drogi[1000000];
int komb[1000000];

int main()
{
    int n, max = 0;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> miasta[i];
    for(int i=0; i<n-1; i++)
        cin >> drogi[i];
    for(int i=0; i<n; i++)
    {
        int droga = 0;
        for(int j=0; j<n-i; j++)
        {
            komb[i+j] = (miasta[i] - miasta[j]) - droga;
            cout << komb[i+j] << " ";
            if(komb[i+j] > max)
                max = komb[i+j];
            droga+=drogi[i+j];
        }
    }
    if(max < 0)
        cout << 0;
    else
        cout << max;
    return 0;
}

Z góry dzięki za pomoc ;)

int miasta[1000000];
int drogi[1000000];
int komb[1000000];

zmień to, bo to strasznie dużo zajmuje.

zapoznaj się z operatorem new i delete[]

int *drogi = new int[5];
///
///
///
delete[] drogi;