Zadanie Kupiec z II etapu IV OIG

Cześć. Potrzebuję pomocy z jednym zadaniem z OIG. Jego treść znajduje się tutaj: http://main.edu.pl/pl/archive/oig/4/kup
Mój problem polega generalnie na tym, że nie mam pojęcia jak rozwiązać te zadanie.

Tak to bywa z konkursami że nie każdy potrafi rozwiązać. Odpuść to zadanie i rób inne a do tego wróć jak trochę przyskillujesz.

Musisz ich dużo zrobić, żeby zaczeły jakoś iść. Co do zadania to bardzo przypomina problem podciągu spójnego o maksymalnej sumie (gdzieś mi zniknęła opcja wstawiania linku: http://main.edu.pl/pl/user.phtml?op=lesson&n=29&page=algorytmika). Przeczytaj to i zastanów się nad tym jeszcze raz. Jeśli nie masz pomysłu na wzorcówkę, zrób najpierw bruta - rozpatrz każdy możliwy początek i koniec o(n^2).

bartek19121995 napisał(a):

Co do zadania to bardzo przypomina problem podciągu spójnego o maksymalnej sumie

Te zadana nawet koło siebie nie leżały. Tutaj możemy kupić dokładnie raz i tyleż samo razy sprzedać.
Rozwiązanie zadania jest dość proste (choć niemiło mi się je pisało). Najpierw trzeba napisać sobie funkcję, która będzie nam zwracała w czasie stałym koszt przejazdu pomiędzy miastem p i q. Możemy to zrobić w czasie liniowym (przygotowanie jej), robiąc tablice sum prefiksowych (i wstawiając na jej początek zero, bo z pierwszego miasta do niego samego koszt to zero). Potem tylko:

  (unsigned p, unsigned q){return abs(koszty[q]-koszty[p])} //Obliczanie kosztu przejazdu między miastami p i q

Teraz trzeba zauważyć, że rozpatrujemy osobno podróże "w lewo" i "w prawo". Zacznijmy od rozpatrzenia podróży "w lewo". Jest to już w zasadzie prawie dynamik. Trzeba tylko zauważyć, że jeśli wyruszamy z pewnego miasta w lewo to albo opłaca się nam iść z tego miasta do miasta, do którego opłacało się iść z poprzedniego (o jeden w lewo), albo w ogóle z niego nie wychodzić. Nie opłaca nam się z niego wychodzić, jeśli koszt zakupu i podróży jest większy od ceny sprzedaży.
Dodatkowy fakt, na który trzeba zwrócić uwagę to ten, że z miasta pierwszego nie wyjdziemy (bo dalej nic nie ma), więc początkowo najlepsze miasto to właśnie ono.

   for(auto i = 0U, najlepsze = i; i != n; ++i) { //najlepszy - miasto do którego opłaca się iść
    if(cena_produktu[najlepsze] < cena_produktu[i] + cena_podrozy(najlepsze, i))
     najlepsze = i; //Nie opłaca się wychodzić w tą stronę
    wynik.push_back(najlepsze);
   }

Teraz jak już wiemy dokąd opłaca nam się iść z każdego miasta, wystarczy przeiterować tablice i wybrać miasto, które daje największy zysk.

 for(unsigned i = 0; i < n; ++i) {
     najwiekszy_zysk = max(najwiekszy_zysk, cena_produktu[w_lewo[i]] - (cena_produktu[i] + cena_podrozy(i,w_lewo[i])));
   }

Problem "w prawo" rozwiązujemy analogicznie, możemy nawet tymi samymi funkcjami jeśli rozsądnie poodwracamy tablice.Na koniec wybieramy max z dwóch wartości, największego zysku jeśli zdecydujemy się iść w prawo oraz największego zysku, jeśli zdecydujemy się iść w lewo.
Może kiedyś tu wrócę i udowodnię poprawność tego rozwiązania, tymczasem musi starczyć to, że jak się je tak rozwiąże i zadba o parę niuansów to uzyskuje się maksymalną liczbę punków.

Edit:
Jeśli ktoś by chciał to umieszczam kod, który pisałem ostatnio na czas:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
 
using namespace std;
 
unsigned wylicz(const vector<unsigned>& towary, const vector<unsigned>& przejazdy);
 
int main() {
        ios_base::sync_with_stdio(false);
        unsigned n;
        cin >> n;
        vector<unsigned> towary(n);
        for(auto& x : towary) // Stare gcc
                cin >> x;
        vector<unsigned> przejazdy = {0}, przejazdy_sum;
        przejazdy.reserve(n+1); przejazdy_sum.reserve(n+1);
        copy_n(istream_iterator<unsigned>(cin), n-1, back_inserter(przejazdy));
        partial_sum(begin(przejazdy), end(przejazdy), back_inserter(przejazdy_sum));
        auto wynik = wylicz(towary, przejazdy_sum);
        reverse(begin(towary), end(towary));
        reverse(begin(przejazdy) + 1, end(przejazdy));
        partial_sum(begin(przejazdy), end(przejazdy), begin(przejazdy_sum));
        wynik = max(wynik, wylicz(towary, przejazdy_sum));
        cout << wynik << '\n';
}
 
unsigned wylicz(const vector<unsigned>& towary, const vector<unsigned>& przejazdy) {
    auto koszt_f = [&przejazdy](unsigned i, unsigned j){return przejazdy[j] - przejazdy[i];};
        unsigned wynik = 0, optymalne = 0;
        for(unsigned i = 0; i < towary.size(); ++i) {
                const auto koszt = towary[optymalne] + koszt_f(optymalne, i);
                if(wynik +  koszt < towary[i]  ) {
                        wynik = towary[i] -  koszt;
                }
                if(towary[i] < towary[optymalne] + koszt_f(optymalne, i)) {
                        optymalne = i;
                }
        }
        return wynik;
}