Aceleração por Matrizes

A otimização via matrizes é fundamental para resolver problemas de recorrência linear em tempo logarítmico. Abaixo, uma implementação base para multiplicação e exponenciação de matrizes quadradas.

#include <iostream>
#include <vector>
#include <cstring>

const int DIM = 3;

struct MatrixContainer {
    long long mat[DIM][DIM];

    MatrixContainer() {
        std::memset(mat, 0, sizeof(mat));
    }

    MatrixContainer operator*(const MatrixContainer& other) const {
        MatrixContainer result;
        for (int i = 0; i < DIM; ++i) {
            for (int k = 0; k < DIM; ++k) {
                if (mat[i][k] == 0) continue;
                for (int j = 0; j < DIM; ++j) {
                    result.mat[i][j] += mat[i][k] * other.mat[k][j];
                }
            }
        }
        return result;
    }
};

void execute_demo() {
    MatrixContainer m1, m2;
    m1.mat[0][0] = 1; 
    m2.mat[0][0] = 1;
    MatrixContainer res = m1 * m2;
    std::cout << res.mat[0][0] << std::endl;
}

Otimização com Estruturas de Dados

Muitas vezes, a transição de um estado de DP depende de consultas de intervalo ou busca por valores específicos. O uso de Árvores de Fenwick (Binary Indexed Trees) pode reduzir a complexidade de uma dimensão inteira.

Exemplo: Subsequências de Tamanho K (CF597C)

O objetivo é contar subsequências de comprimento fixo. A árvore de Fenwick elimina a necessidade de iterar sobre todos os elementos anteriores para verificar a condição de ordem.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_VAL = 100005;
const int MAX_LEN = 15;

long long bit_table[MAX_LEN][MAX_VAL];
int limit_n;

void update_bit(int len, int idx, long long val) {
    for (; idx <= limit_n; idx += idx & -idx)
        bit_table[len][idx] += val;
}

long long query_bit(int len, int idx) {
    long long sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit_table[len][idx];
    return sum;
}

int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    limit_n = n;
    k++; 

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        update_bit(1, x, 1);
        for (int j = 2; j <= k; ++j) {
            long long prev_count = query_bit(j - 1, x - 1);
            update_bit(j, x, prev_count);
        }
    }

    cout << query_bit(k, limit_n) << endl;
    return 0;
}

Otimização de Inclinação (Slope Optimization)

Esta técnica é aplicada quando a transição da DP possui a forma $dp[i] = \min \{ dp[j] + f(i, j) \}$, onde $f(i, j)$ pode ser linearizada. O problema é transformado na manutenção de um invólucro convexo (convex hull).

Exemplo: Toy Packing (HNOI2008)

A equação de custo pode ser reescrita na forma $y = mx + c$. Mantemos um conjunto de pontos e utilizaoms uma fila monótona para encontrar o ponto que minimiza o intercepto.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 50005;
ll prefix_sum[MAXN], dp_val[MAXN], coord_a[MAXN], coord_b[MAXN];
int deque_idx[MAXN];

double calculate_slope(int i, int j) {
    double dy = (double)(dp_val[i] + coord_b[i] * coord_b[i]) - (dp_val[j] + coord_b[j] * coord_b[j]);
    double dx = (double)coord_b[i] - coord_b[j];
    return dy / dx;
}

int main() {
    int n;
    ll L;
    cin >> n >> L;

    for (int i = 1; i <= n; ++i) {
        ll weight;
        cin >> weight;
        prefix_sum[i] = prefix_sum[i - 1] + weight;
        coord_a[i] = prefix_sum[i] + i;
        coord_b[i] = prefix_sum[i] + i + 1 + L;
    }

    coord_b[0] = 1 + L;
    int head = 0, tail = 0;
    deque_idx[0] = 0;

    for (int i = 1; i <= n; ++i) {
        while (head < tail && calculate_slope(deque_idx[head + 1], deque_idx[head]) < 2.0 * coord_a[i]) 
            head++;
        
        int best_j = deque_idx[head];
        ll diff = coord_a[i] - coord_b[best_j];
        dp_val[i] = dp_val[best_j] + diff * diff;

        while (head < tail && calculate_slope(i, deque_idx[tail]) < calculate_slope(deque_idx[tail], deque_idx[tail - 1])) 
            tail--;
        deque_idx[++tail] = i;
    }

    cout << dp_val[n] << endl;
    return 0;
}

Lidando com Coeficientes não Monótonos

Quando a inclinação ou a coordenada X não são monótonas, a fila monótona tradicional falha. Nesses casos, utilizamos busca binária sobre o invólucro convexo ou estruturas mais complexas como a Li Chao Tree.

Exemplo: Agendamento de Tarefas com Custos Variáveis

Se o tempo de processamento puder ser negativo, o coeficiente angular deixa de ser monótono. A busca binária é necessária para encontrar o segmento correto do invólucro.

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MAXN = 300005;

ll T[MAXN], C[MAXN], dp[MAXN];
int q[MAXN];

double get_slope(int i, int j) {
    if (C[i] == C[j]) return 1e18;
    return (double)(dp[i] - dp[j]) / (C[i] - C[j]);
}

int binary_search_hull(int l, int r, ll target_slope) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (get_slope(q[mid + 1], q[mid]) <= target_slope) l = mid + 1;
        else r = mid;
    }
    return q[l];
}

int main() {
    int n;
    ll s;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        ll ti, ci;
        cin >> ti >> ci;
        T[i] = T[i - 1] + ti;
        C[i] = C[i - 1] + ci;
    }

    int head = 0, tail = 0;
    q[0] = 0;

    for (int i = 1; i <= n; ++i) {
        int best_j = binary_search_hull(head, tail, s + T[i]);
        dp[i] = dp[best_j] + T[i] * (C[i] - C[best_j]) + s * (C[n] - C[best_j]);

        while (head < tail && get_slope(i, q[tail]) <= get_slope(q[tail], q[tail - 1])) 
            tail--;
        q[++tail] = i;
    }

    cout << dp[n] << endl;
    return 0;
}