Omówienie zadania Wyrażenie arytmetyczne (I etap XXXIII OI, tura szkolna)

Rozwiązanie brutalne

Zauważmy, że dla \(n\geq 2\) wyrażenie wyliczające się do \(n\) możemy otrzymać na dwa sposoby:

1. jako sumę dwóch wyrażeń wyliczających się do \(k\) oraz \(n-k\) dla pewnego całkowitego \(k\) z zakresu \(1 \leq k < n\) lub
2. jako iloczyn dwóch wyrażeń wyliczający się do \(k\) oraz \(\frac{n}{k}\) dla pewnego całkowitego \(k\) z zakresu \(1 < k < n\) będącego dzielnikiem liczby \(n\).

Ta obserwacja prowadzi nas do rozwiązania rekurencyjnego. Niech \(oblicz(n)\) będzie funkcją zwracającą minimalny koszt wyrażenia wyliczającego się do \(n\). Wówczas oczywiście mamy \(oblicz(1) = a\), natomiast dla \(n \geq 2\) możemy zapisać: \[ oblicz(n) = \min \left( \min_{1 \leq k < n} \left( oblicz(k) + oblicz(n-k) + b \right), \min_{\substack{1 < k < n \\ k | n}} \left( oblicz(k) + oblicz\left(\frac{n}{k}\right) + c \right) \right), \] co można zaimplementować w języku C++ w następujący sposób:

const long long inf = 1ll << 60;

long long a, b, c;

long long oblicz(int n) {
    if (n == 1)
        return a;
    long long wynik = inf;
    for (int k = 1; k < n; k++) {
        wynik = min(wynik, oblicz(k) + oblicz(n - k) + b);
    }
    for (int k = 2; k < n; k++) {
        if (n % k == 0) {
            wynik = min(wynik, oblicz(k) + oblicz(n / k) + c);
        }
    }
    return wynik;
}

int main() {
    int n;
    cin >> n >> a >> b >> c;
    for (int i = 1; i <= n; i++) {
        cout << oblicz(i) << " ";
    }
    cout << "\n";
}

Takie rozwiązanie jest poprawne, jednak jego złożoność czasowa jest wykładnicza, więc nie pozwalało ono uzyskać maksymalnej liczby punktów w tym zadaniu.

Rozwiązanie wzorcowe

Zauważmy, że powyższy program będzie wywoływał funkcję \(oblicz\) dla tej samej wartości \(n\) wielokrotnie, przez co będzie wykonywał te same obliczenia wiele razy. Aby temu zapobiec, możemy zastosować technikę zwaną spamiętywaniem (ang. memoization). Polega ona na zapamiętywaniu wyników obliczeń funkcji dla poszczególnych wartości argumentów, tak aby przy kolejnych wywołaniach z tymi samymi argumentami zwracać już zapamiętany wynik zamiast ponownie wykonywać obliczenia. Wprowadźmy więc tablicę liczb całkowitych \(mem\), gdzie \(mem[n]=-1\), jeśli funkcja \(oblicz(n)\) nie była jeszcze wywołana, a w przeciwnym wypadku \(mem[n]\) będzie przechowywać wynik wywołania funkcji \(oblicz(n)\). Takie rozwiązanie możemy zaimplementować następująco:

const long long inf = 1ll << 60;
const int MAX_N = 3001;

long long a, b, c;

long long mem[MAX_N];

long long oblicz(int n) {
    if (n == 1)
        return a;
    if (mem[n] != -1)
        return mem[n]; // Zwracamy wcześniej obliczony wynik.
    long long wynik = inf;
    for (int k = 1; k < n; k++) {
        wynik = min(wynik, oblicz(k) + oblicz(n - k) + b);
    }
    for (int k = 2; k < n; k++) {
        if (n % k == 0) {
            wynik = min(wynik, oblicz(k) + oblicz(n / k) + c);
        }
    }
    mem[n] = wynik; // Zapamiętujemy wynik przed zwróceniem go.
    return wynik;
}

int main() {
    int n;
    cin >> n >> a >> b >> c;
    fill(mem, mem + n + 1, -1);
    for (int i = 1; i <= n; i++) {
        cout << oblicz(i) << " ";
    }
    cout << "\n";
}

Powyższy algorytm działa w złożoności \(O(n^2)\), ponieważ wartości funkcji \(oblicz\) są teraz efektywnie obliczane tylko raz dla każdej wartości jej argumentu, a samo obliczenie wartości funkcji zajmuje czas \(O(n)\) (pomijając czas wywołań rekurencyjnych). Takie rozwiązanie pozwala uzyskać maksymalną liczbę punktów za to zadanie.