Wyrażenie arytmetyczne w O(n lg n)

W etapie szkolnym XXXIII Olimpiady Informatycznej pojawiło się zadanie Wyrażenie Arytmetyczne. Zadanie to można było rozwiązać programowaniem dynamicznym w czasie O(n²). Zadanie to nie sprawiło zawodnikom wielu trudności. Mało kto jednak wie, że zadanie to można rozwiązać w czasie O(n lg n). Prezentuje to poniższy kod:

vector<long long> dynamic(int a, int b, int c, int n) // O(n log n)
{
    vector<long long> dp(n + 1, oo);

    dp[1] = a;

    for (int i = 1; i < n; i++)
    {
        dp[i + 1] = min(dp[i + 1], dp[i] + a + b);
        for (int j = 1; i * j <= n; j++)
            dp[i * j] = min(dp[i * j], dp[i] + dp[j] + c);
    }

    return dp;
}