Seleção com Restrição de Contagem (CodeVS 4815)

Este exercício aborda a escolha de elementos respeiatndo um limite fixo k. Como a entrada pode conter valores negativos, a tabela de estados deve ser inicializada com um valor suficientemente baixo para evitar a propagação de transições inválidas. A estrutura utiliza três dimensões: índice processado, quantidade selecionada e um flag indicando a inclusão do elemento atual.

#include <cstdio>
#include <algorithm>
using namespace std;

constexpr long long INF_NEG = -1e18;
constexpr int LIM = 1005;
long long dp[LIM][LIM][2];
long long val[LIM];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%lld", &val[i]);

    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            dp[i][j][0] = dp[i][j][1] = INF_NEG;

    for (int j = 0; j <= k; ++j) dp[0][j][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]);
            if (j > 0) {
                dp[i][j][1] = max(dp[i-1][j-1][0] + val[i], dp[i][j][1]);
            }
        }
    }
    printf("%lld\n", max(dp[n][k][0], dp[n][k][1]));
    return 0;
}

Otimização de Custos com Alternância de Ferramentas (CodeVS 1695)

O algoritmo calcula o custo mínimo para processar n itens, permitindo a escolha entre dois métodos por etapa. A troca entre métodos consecutivos incorre em uma penalidade. Mantém-se apenas o estado anterior na memória para determinar o caminho de menor custo até o índice atual.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

constexpr long long INF_POS = 0x3f3f3f3f3f3f3f3f;
constexpr int MAX_MEALS = 105;
long long state[MAX_MEALS][2];
long long costA[MAX_MEALS], costB[MAX_MEALS], penalty[MAX_MEALS];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld %lld %lld", &costA[i], &costB[i], &penalty[i]);

    memset(state, 0x3f, sizeof(state));
    state[1][0] = costA[1] + penalty[1];
    state[1][1] = costB[1];

    for (int i = 2; i <= n; ++i) {
        state[i][0] = min(state[i-1][1] + penalty[i] + costA[i], state[i-1][0] + costA[i]);
        state[i][1] = min(state[i-1][0] + penalty[i] + costB[i], state[i-1][1] + costB[i]);
    }
    printf("%lld\n", min(state[n][0], state[n][1]));
    return 0;
}

Alocação de Recursos entre Empresas (Luogu 2066)

Dadas n entidades e m unidades de recurso, o objetivo é maximizar o retorno total. O estado opt[i][j] registra o benefício ótimo ao distribuir j recursos considerando as primeiras i entidades. Para garantir a saída em ordem lexicográfica, armazena-se a quantidade exata alocada em cada etapa durante a construção da tabela.

#include <cstdio>
using namespace std;

constexpr int MAX_ENT = 20, MAX_RES = 20;
long long profit[MAX_ENT][MAX_RES], opt[MAX_ENT][MAX_RES];
int allocation[MAX_ENT][MAX_RES];

int main() {
    int ent, res;
    scanf("%d %d", &ent, &res);
    for (int i = 1; i <= ent; ++i)
        for (int j = 1; j <= res; ++j)
            scanf("%lld", &profit[i][j]);

    for (int i = 1; i <= ent; ++i) {
        for (int j = 0; j <= res; ++j) {
            opt[i][j] = opt[i-1][j];
            allocation[i][j] = 0;
            for (int k = 1; k <= j; ++k) {
                long long cur = opt[i-1][j-k] + profit[i][k];
                if (cur > opt[i][j]) {
                    opt[i][j] = cur;
                    allocation[i][j] = k;
                }
            }
        }
    }
    printf("%lld\n", opt[ent][res]);
    int rem = res;
    for (int i = 1; i <= ent; ++i) {
        printf("%d %d\n", i, allocation[i][rem]);
        rem -= allocation[i][rem];
    }
    return 0;
}

Segmentação de Sequências com Restrição de Diferença (Luogu 1564)

O problema exige a divisão de uma lista em segmentos válidos, onde cada grupo contém exclusivamente um tipo de elemento ou apresenta uma diferença de frequência inferior a m. Somas prefixais são pré-calculadas para verificar a condição em tempo constante durante a transição do estado.

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

constexpr int MAX_SZ = 2505;
int cnt1[MAX_SZ], cnt2[MAX_SZ], dp[MAX_SZ];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int type;
        scanf("%d", &type);
        cnt1[i] = cnt1[i-1] + (type == 1);
        cnt2[i] = cnt2[i-1] + (type == 2);
        dp[i] = i;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            int diff1 = cnt1[i] - cnt1[j];
            int diff2 = cnt2[i] - cnt2[j];
            if (diff1 == i - j || diff2 == i - j || abs(diff1 - diff2) <= m) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

Soma Máxima de Subsegmento Contíguo (Luogu 1115)

Implementação direta da técnica de Kadane. O vetor current[i] armazena a maior soma de um subarray que termina exatamente na possição i. A cada iteração, avalia-se se estender o subarray anterior é mais vantajoso do que iniciar um novo a partir do elemento corrente.

#include <cstdio>
#include <algorithm>
using namespace std;

constexpr int MAX_LEN = 200005;
int seq[MAX_LEN], current[MAX_LEN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &seq[i]);
    
    int global_best = -2147483648;
    current[0] = 0;
    for (int i = 1; i <= n; ++i) {
        current[i] = max(current[i-1] + seq[i], seq[i]);
        global_best = max(global_best, current[i]);
    }
    printf("%d\n", global_best);
    return 0;
}

Duas Subsequências Disjuntas com Soma Máxima (POJ 2479)

A estratégia calcula, de forma independente, a soma máxima contígua que se estende da esquerda para a direita e vice-versa. Ao percorrer todos os índices de corte possíveis, soma-se o melhor valor do prefixo esquerdo com o melhor valor do sufixo direito, isolando dois intervalos não sobrepostos.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

constexpr int MAX_ARR = 50005;
int data[MAX_ARR], prefixEnd[MAX_ARR], suffixEnd[MAX_ARR];
int prefixBest[MAX_ARR], suffixBest[MAX_ARR];

int main() {
    int cases;
    scanf("%d", &cases);
    while (cases--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &data[i]);

        prefixEnd[1] = data[1];
        prefixBest[1] = data[1];
        for (int i = 2; i <= n; ++i) {
            prefixEnd[i] = max(prefixEnd[i-1] + data[i], data[i]);
            prefixBest[i] = max(prefixBest[i-1], prefixEnd[i]);
        }

        suffixEnd[n] = data[n];
        suffixBest[n] = data[n];
        for (int i = n - 1; i >= 1; --i) {
            suffixEnd[i] = max(suffixEnd[i+1] + data[i], data[i]);
            suffixBest[i] = max(suffixBest[i+1], suffixEnd[i]);
        }

        int answer = -2147483648;
        for (int i = 1; i < n; ++i) {
            answer = max(answer, prefixBest[i] + suffixBest[i+1]);
        }
        printf("%d\n", answer);
    }
    return 0;
}