Programação Dinâmica em Intervalos Circulares

A resolução de problemas envolvendo estruturas circulares frequentemente requer a técnica de duplicação do array de entrada para simular o anel linearmente. Para este problema, o primeiro passo é pré-processar a contagem de elementos distintos em todos os intervalos possíveis, o que pode ser realizado em $O(n^3)$. Em seguida, aplica-se a Programação Dinâmica em Intervalos para calcular o lucro máximo de combinações.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> elements(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> elements[i];
        elements[i + n] = elements[i];
    }

    vector<vector<int>> distinct_count(2 * n, vector<int>(2 * n, 0));
    for (int i = 0; i < 2 * n; ++i) {
        vector<bool> seen(n + 1, false);
        int count = 0;
        for (int j = i; j < 2 * n; ++j) {
            if (!seen[elements[j]]) {
                seen[elements[j]] = true;
                count++;
            }
            distinct_count[i][j] = count;
        }
    }

    vector<vector<int>> dp(2 * n, vector<int>(2 * n, 0));
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < 2 * n; ++i) {
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + distinct_count[i][k] * distinct_count[k + 1][j]);
            }
        }
    }

    int max_profit = 0;
    for (int i = 0; i < n; ++i) {
        max_profit = max(max_profit, dp[i][i + n - 1]);
    }
    cout << max_profit << "\n";
    return 0;
}

Otimização Geométrica em Grade Hexagonal

O problema de minimizar o perímetro ao posicionar elementos em uma grade hexagonal exige uma abordagem matemática e gulosa. Para maximizar as arestas compartilhadas, os elementos devem ser agrupados da forma mais compacta possível, formando hexágonos concêntricos. O algoritmo calcula primeiro o maior hexágono completo que pode ser formado e, em seguida, distribui os elementos restantes ao redor da borda externa de forma gulosa para minimizar o perímetro resultante.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long total_elements;
    if (!(cin >> total_elements)) return 0;

    long long layer = 0;
    long long current_capacity = 1;
    long long perimeter = 0;

    while (true) {
        long long next_layer_elements = 6 * (layer + 1);
        if (current_capacity + next_layer_elements > total_elements) {
            perimeter = 6 * (layer + 1);
            long long remaining = total_elements - current_capacity;
            if (remaining > 0) {
                perimeter += (remaining / (layer + 1)) + (remaining % (layer + 1) > 0 ? 2 : 0);
            }
            break;
        }
        current_capacity += next_layer_elements;
        layer++;
    }

    if (total_elements == 0) perimeter = 0;
    cout << perimeter << "\n";
    return 0;
}

Teoria dos Grafos e Florestas de Anéis

Este problema pode ser modelado como um grafo funcional, onde cada nó possui exatamente uma aresta de saída, resultando em uma floresta de árvores com anéis. A estratégia inicial é gulosa: coletar todo o lucro possível dos nós que possuem estoque maior que um. Após isso, o grafo se resume a cadeias e anéis simples. Os nós em cadeias podem ter seu lucro totalmente coletado. Para os anéis, é necessário abrir o ciclo, o que implica renunciar ao lucro de um nó. O algoritmo de Tarjan é utilizado para identificar e contrair os componentes fortemente conectados, faciiltando o cálculo do lucro máximo.

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

using namespace std;

struct Item {
    int target;
    int cost;
    int price;
    int stock;
};

int n;
vector<Item> items;
vector<vector<pair<int, int>>> graph;
vector<int> dfn, low, scc_id, scc_size;
vector<long long> scc_value;
int timer_cnt = 0, scc_count = 0;
vector<int> st;
vector<bool> in_st;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer_cnt;
    st.push_back(u);
    in_st[u] = true;

    for (auto& edge : graph[u]) {
        int v = edge.first;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_st[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_count++;
        int v;
        do {
            v = st.back();
            st.pop_back();
            in_st[v] = false;
            scc_id[v] = scc_count;
            scc_size[scc_count]++;
            scc_value[scc_count] += items[v].price - items[v].cost;
        } while (v != u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> n)) return 0;

    items.resize(n + 1);
    graph.resize(n + 1);
    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    scc_size.assign(n + 1, 0);
    scc_value.assign(n + 1, 0);
    st.reserve(n + 1);
    in_st.assign(n + 1, false);

    long long total_profit = 0;
    vector<pair<int, int>> best_edges(n + 1, {0, 0});

    for (int i = 1; i <= n; ++i) {
        cin >> items[i].target >> items[i].cost >> items[i].price >> items[i].stock;
        if (items[i].stock > 1) {
            total_profit += (long long)(items[i].stock - 1) * (items[i].price - items[i].cost);
            items[i].stock = 1;
        }
    }

    for (int i = 1; i <= n; ++i) {
        int profit = items[items[i].target].price - items[i].cost;
        if (profit > 0 && profit > best_edges[items[i].target].first) {
            best_edges[items[i].target] = {profit, i};
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (best_edges[i].first > 0) {
            graph[best_edges[i].second].push_back({i, best_edges[i].first});
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i);
    }

    for (int i = 1; i <= scc_count; ++i) {
        total_profit += scc_value[i];
    }

    cout << total_profit << "\n";
    return 0;
}

DP em Strings e Busca de Padrões

Abordagens gulosas simples para eliminação de substrings falham devido a sobreposições e padrões não contíguos. A solução correta utiliza Programação Dinâmica em Intervalos com busca memoizada. Para um comprimento de substring candidato $d$, definimos o estado $dp[i][j]$ para verificar se o intervalo $[i, j]$ pode ser completamente eliminado. As transições ocorrem de duas formas: correspondência caractere a caractere ou correspondência em blocos de tamanho $d$. A ordem das transições é crucial para a correção do algoritmo, exigindo que a verificação em blocos seja processada antes da verificação caractere a caractere.

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

using namespace std;

int n;
string s;
vector<vector<int>> memo;

bool can_eliminate(const string& pattern, int l, int r) {
    if (l > r) return true;
    if (memo[l][r] != -1) return memo[l][r];

    int d = pattern.length();

    for (int k = r - d; k >= l; k -= d) {
        if (can_eliminate(pattern, l, k) && can_eliminate(pattern, k + 1, r)) {
            return memo[l][r] = 1;
        }
    }

    if (s[r] == pattern[(r - l) % d]) {
        if (can_eliminate(pattern, l, r - 1)) {
            return memo[l][r] = 1;
        }
    }

    return memo[l][r] = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (!(cin >> t)) return 0;

    while (t--) {
        cin >> s;
        n = s.length();
        string best_pattern = "";

        for (int d = 1; d <= n; ++d) {
            if (n % d != 0) continue;

            bool found = false;
            for (int i = 0; i + d <= n; ++i) {
                string pattern = s.substr(i, d);
                memo.assign(n, vector<int>(n, -1));

                if (can_eliminate(pattern, 0, n - 1)) {
                    if (best_pattern.empty() || pattern < best_pattern) {
                        best_pattern = pattern;
                    }
                    found = true;
                }
            }
            if (found) break;
        }
        cout << best_pattern << "\n";
    }
    return 0;
}