1. Fusão de Caracteres (HAOI2016)

Neste problema, temos uma string binária de comprimento $n$. Podemos fundir $k$ caracteres adjacentes em um único caractere, ganhando pontos baseados no resultado da fusão e na sequência original. O objetivo é maximizar a pontuação total.

Dado que $k \le 8$, podemos utilizar compressão de estado (bitmask) para representar o resultado da fusão de um intervalo. Definimos $dp[l][r][mask]$ como a pontuação máxima para reduzir o intervalo $[l, r]$ ao estado binário representado por mask. O comprimento final de uma sequência após sucessivas fusões de $k$ elementos pode ser determinado por $(len-1) \pmod{k-1} + 1$.

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

using namespace std;

typedef long long ll;
const ll NEG_INF = -1e17;

ll n, k;
int sequence[305];
int target_char[256];
ll rewards[256];
ll memo[305][305][256];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> sequence[i];
    for (int i = 0; i < (1 << k); ++i) cin >> target_char[i] >> rewards[i];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int s = 0; s < (1 << k); ++s)
                memo[i][j][s] = NEG_INF;

    for (int i = n; i >= 1; --i) {
        for (int j = i; j <= n; ++j) {
            if (i == j) {
                memo[i][j][sequence[i]] = 0;
                continue;
            }
            int len = (j - i) % (k - 1);
            if (len == 0) len = k - 1;

            for (int mid = j; mid > i; mid -= (k - 1)) {
                for (int s = 0; s < (1 << len); ++s) {
                    if (memo[i][mid - 1][s] == NEG_INF) continue;
                    if (memo[mid][j][0] != NEG_INF)
                        memo[i][j][s << 1] = max(memo[i][j][s << 1], memo[i][mid - 1][s] + memo[mid][j][0]);
                    if (memo[mid][j][1] != NEG_INF)
                        memo[i][j][s << 1 | 1] = max(memo[i][j][s << 1 | 1], memo[i][mid - 1][s] + memo[mid][j][1]);
                }
            }

            if (len == k - 1) {
                ll best[2] = {NEG_INF, NEG_INF};
                for (int s = 0; s < (1 << k); ++s) {
                    if (memo[i][j][s] != NEG_INF)
                        best[target_char[s]] = max(best[target_char[s]], memo[i][j][s] + rewards[s]);
                }
                memo[i][j][0] = best[0];
                memo[i][j][1] = best[1];
            }
        }
    }

    ll total_max = NEG_INF;
    for (int s = 0; s < (1 << k); ++s) total_max = max(total_max, memo[1][n][s]);
    cout << total_max << endl;
}

2. Minimização de Custo em Sequências (THUSC2016)

Dada uma sequência de notas $a[1..n]$, podemos remover subsegmentos contínuos. O custo de remover um segmento é dado por $A + B \times (max - min)^2$. Precisamos encontrar o custo mínimo para remover todos os elementos.

Utilizamos DP de intervalo. Seja $f[l][r]$ o custo mínimo para limpar o intervalo $[l, r]$. Para auxiliar, definimos $g[l][r][mn][mx]$ como o custo mínimo para reduzir o intervalo $[l, r]$ a um estado onde os valores restentes têm mínimo $mn$ e máximo $mx$.

#include <bits/stdc++.h>
using namespace std;

int n, costA, costB;
int val[55], sorted_vals[55], total_unique;
int dp_full[55][55], dp_range[55][55][55][55];

int main() {
    cin >> n >> costA >> costB;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        sorted_vals[i] = val[i];
    }
    sort(sorted_vals + 1, sorted_vals + n + 1);
    total_unique = unique(sorted_vals + 1, sorted_vals + n + 1) - sorted_vals - 1;
    
    memset(dp_range, 0x3f, sizeof dp_range);
    memset(dp_full, 0x3f, sizeof dp_full);

    for (int i = 1; i <= n; i++) {
        val[i] = lower_bound(sorted_vals + 1, sorted_vals + total_unique + 1, val[i]) - sorted_vals;
        dp_range[i][i][val[i]][val[i]] = 0;
        dp_full[i][i] = costA;
    }

    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int mn = 1; mn <= total_unique; mn++) {
                for (int mx = mn; mx <= total_unique; mx++) {
                    if (dp_range[l][r][mn][mx] > 1e9) continue;
                    // Tenta expandir ou combinar
                    for (int k = r + 1; k <= n; k++) {
                        dp_range[l][k][min(mn, val[k])][max(mx, val[k])] = min(dp_range[l][k][min(mn, val[k])][max(mx, val[k])], dp_range[l][r][mn][mx] + dp_full[r+1][k-1]);
                    }
                    int diff = sorted_vals[mx] - sorted_vals[mn];
                    dp_full[l][r] = min(dp_full[l][r], dp_range[l][r][mn][mx] + costA + costB * diff * diff);
                }
            }
            // Transição extra para f[l][r] influenciar outros g
            for (int mn = 1; mn <= total_unique; mn++)
                for (int mx = mn; mx <= total_unique; mx++)
                    for (int k = l; k < r; k++)
                        dp_range[l][r][mn][mx] = min(dp_range[l][r][mn][mx], dp_range[l][k][mn][mx] + dp_full[k+1][r]);
        }
    }
    cout << dp_full[1][n] << endl;
    return 0;
}

3. Mapeamento de Árvore em Grafo (ZJOI2016)

O desafio consiste em contar quantos mapeamentos de uma árvore de $n$ nós em um grafo de $n$ nós existem, tal que se $(u, v)$ é uma aresta na árvore, seus mapeamentos devem ser adjacentes no grafo. Isso deve ser uma permutação.

Usamos o Princípio da Inclusão-Exclusão sobre o conjunto de nós do grafo permitidos para o mapeamento. Para um subconjunto fixo de nós, aplicamos DP em árvore para contar os mapeamentos válidos.

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

using namespace std;

typedef long long ll;
int n, m;
vector<int> adj_graph[20], adj_tree[20];
ll dp[20][20];
bool active[20];

void compute_dp(int u, int p) {
    for (int i = 1; i <= n; i++) dp[u][i] = active[i] ? 1 : 0;
    for (int v : adj_tree[u]) {
        if (v == p) continue;
        compute_dp(v, u);
        for (int i = 1; i <= n; i++) {
            if (!active[i]) continue;
            ll sum_v = 0;
            for (int neighbor : adj_graph[i]) {
                if (active[neighbor]) sum_v += dp[v][neighbor];
            }
            dp[u][i] *= sum_v;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj_graph[u].push_back(v);
        adj_graph[v].push_back(u);
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj_tree[u].push_back(v);
        adj_tree[v].push_back(u);
    }

    ll total_ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if ((s >> i) & 1) {
                active[i + 1] = true;
                cnt++;
            } else active[i + 1] = false;
        }
        compute_dp(1, 0);
        ll current_set_sum = 0;
        for (int i = 1; i <= n; i++) current_set_sum += dp[1][i];
        if ((n - cnt) % 2 == 1) total_ans -= current_set_sum;
        else total_ans += current_set_sum;
    }
    cout << total_ans << endl;
    return 0;
}

4. Seleção Ótima de Itens em Prefixos (CF1442D)

Temos $n$ arrays não decrescentes. Queremos escolher $k$ elementos no total para maximizar a soma, respeitando a regra de que só podemos pegar elementos do início de cada array. Como os arrays são não decrescentes, a estrratégia ótima sempre envolverá pegar arrays completos, exceto no máximo um.

Utilizamos uma técnica de Dividir e Conquistar para evitar o recalcular da mochila 0/1 repetidamente.

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

using namespace std;

typedef long long ll;
int n, k;
vector<int> arrays[3005];
ll array_sum[3005];
ll best_total = 0;
ll dp_knapsack[3005];

void solve_recursive(int l, int r, vector<ll> current_dp) {
    if (l == r) {
        ll current_prefix = 0;
        best_total = max(best_total, current_dp[k]);
        for (int i = 0; i < min((int)arrays[l].size(), k); i++) {
            current_prefix += arrays[l][i];
            best_total = max(best_total, current_prefix + current_dp[k - (i + 1)]);
        }
        return;
    }
    int mid = (l + r) >> 1;
    
    vector<ll> left_dp = current_dp;
    for (int i = mid + 1; i <= r; i++) {
        int weight = arrays[i].size();
        for (int j = k; j >= weight; j--)
            left_dp[j] = max(left_dp[j], left_dp[j - weight] + array_sum[i]);
    }
    solve_recursive(l, mid, left_dp);

    vector<ll> right_dp = current_dp;
    for (int i = l; i <= mid; i++) {
        int weight = arrays[i].size();
        for (int j = k; j >= weight; j--)
            right_dp[j] = max(right_dp[j], right_dp[j - weight] + array_sum[i]);
    }
    solve_recursive(mid + 1, r, right_dp);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int t; cin >> t;
        for (int j = 0; j < t; j++) {
            int x; cin >> x;
            if (j < k) {
                arrays[i].push_back(x);
                array_sum[i] += x;
            }
        }
    }
    vector<ll> initial_dp(k + 1, 0);
    solve_recursive(1, n, initial_dp);
    cout << best_total << endl;
    return 0;
}

5. DP em DP: Problema da Quermesse (TJOI2018)

Este problema pede o número de strings de comprimento $n$ (alfabeto $\{N, O, I\}$) que não contêm "NOI" e possuem uma Longest Common Subsequence (LCS) de comprimento $i$ com uma string padrão $s$.

A "DP interna" é o cálculo padrão da LCS. Como a diferença entre $dp[i][j]$ e $dp[i][j-1]$ é apenas 0 ou 1, podemos comprimir o estado da linha da LCS em um bitmask. A "DP externa" transita entre esses estados de bitmask conforme adicionamos caracteres.

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

using namespace std;

const int MOD = 1e9 + 7;
int n, k;
string s;
int trans[1 << 15][3];
int dp[2][1 << 15][3];

int get_next_mask(int mask, int char_idx) {
    static int g[20], h[20];
    for (int i = 0; i < k; i++) g[i + 1] = g[i] + ((mask >> i) & 1);
    for (int i = 1; i <= k; i++) {
        h[i] = max(h[i - 1], g[i]);
        if (s[i - 1] == "NOI"[char_idx]) h[i] = max(h[i], g[i - 1] + 1);
    }
    int next_mask = 0;
    for (int i = 1; i <= k; i++) if (h[i] > h[i - 1]) next_mask |= (1 << (i - 1));
    return next_mask;
}

int main() {
    cin >> n >> k >> s;
    for (int m = 0; m < (1 << k); m++) {
        for (int c = 0; c < 3; c++) trans[m][c] = get_next_mask(m, c);
    }

    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        int curr = i & 1, next = (i + 1) & 1;
        memset(dp[next], 0, sizeof(dp[next]));
        for (int m = 0; m < (1 << k); m++) {
            for (int state = 0; state < 3; state++) {
                if (!dp[curr][m][state]) continue;
                for (int c = 0; c < 3; c++) {
                    int n_mask = trans[m][c];
                    int n_state = 0;
                    if (c == 0) n_state = 1;
                    else if (c == 1 && state == 1) n_state = 2;
                    else if (c == 2 && state == 2) continue; // Forma "NOI"
                    else if (c == 1) n_state = 0; // "O" sem "N" antes
                    
                    dp[next][n_mask][n_state] = (dp[next][n_mask][n_state] + dp[curr][m][state]) % MOD;
                }
            }
        }
    }

    vector<int> results(k + 1, 0);
    for (int m = 0; m < (1 << k); m++) {
        int lcs_len = __builtin_popcount(m);
        for (int s = 0; s < 3; s++) results[lcs_len] = (results[lcs_len] + dp[n & 1][m][s]) % MOD;
    }

    for (int i = 0; i <= k; i++) cout << results[i] << endl;
    return 0;
}