P2340 [USACO03FALL] Cow Exhibition G Enunciado: Dadas N vacas, cada uma com QI S e QE F, selecione algumas vacas de modo que a soma dos QIs e a soma dos QEs sejam ambas positivas, maximziando a soma total (S + F). Abordagem: Podemos tratar o QI como peso e o QE como valor, resolvendo um problema de mochila 0/1. Como o QI pode ser negativo, usamos um deslocamento para evitar índices negativos no array de DP. Para cada vaca, se o QI for não negativo, percorremos o array de trás para frente; caso contrário, percorremos de frente para trás para garantir a correta atualização.

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

const int SHIFT = 400000;
const int MAX_SIZE = 2 * SHIFT + 1;
const int MAX_INDEX = MAX_SIZE - 1;

struct Vaca {
    int qi, qe;
};

int main() {
    int n;
    cin >> n;
    vector<Vaca> vacas(n);
    for (int i = 0; i < n; i++) {
        cin >> vacas[i].qi >> vacas[i].qe;
    }
    vector<ll> dp(MAX_SIZE, -1e18);
    dp[SHIFT] = 0;
    for (const auto& vaca : vacas) {
        if (vaca.qi >= 0) {
            for (int j = MAX_INDEX; j >= vaca.qi; j--) {
                dp[j] = max(dp[j], dp[j - vaca.qi] + vaca.qe);
            }
        } else {
            for (int j = 0; j <= MAX_INDEX + vaca.qi; j++) {
                dp[j] = max(dp[j], dp[j - vaca.qi] + vaca.qe);
            }
        }
    }
    ll resposta = -1e18;
    for (int i = SHIFT; i <= MAX_INDEX; i++) {
        if (dp[i] >= 0) {
            resposta = max(resposta, dp[i] + i - SHIFT);
        }
    }
    cout << resposta << endl;
    return 0;
}

P3188 [HNOI2007] 梦幻岛宝珠 Enunciado: Dadas n gemas com pesos w (≤ 2^30) que podem ser expressos como a * 2^b, e valores v, selecione um subconjunto com peso total ≤ W maximizando o valor total. Abordagem: Como o peso é da forma a * 2^b, agrupamos as gemas pelo expoente b (a posição do bit menos significativo do peso). Para cada grupo, realizamos uma mochila 0/1 nos coeficientes a. Em seguida, combinamos os grupos usando DP por bits, considerando a restrição do peso W. A ideia é que, ao passar de um bit para o próximo, o peso restante é multiplicado por 2 e ajustado pelo bit correspondente de W.

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

const int MAX_BIT = 30;
const int MAX_COEFF = 1000;

int main() {
    int n, W;
    while (cin >> n >> W, n != -1 || W != -1) {
        vector<vector<pair<int, int>>> grupos(MAX_BIT + 1);
        for (int i = 0; i < n; i++) {
            int peso, valor;
            cin >> peso >> valor;
            int b = 0;
            while ((peso & 1) == 0) {
                peso >>= 1;
                b++;
            }
            grupos[b].push_back({peso, valor});
        }

        vector<vector<ll>> valorGrupo(MAX_BIT + 1, vector<ll>(MAX_COEFF + 1, 0));
        for (int b = 0; b <= MAX_BIT; b++) {
            for (const auto& gema : grupos[b]) {
                int coef = gema.first;
                int val = gema.second;
                for (int w = MAX_COEFF; w >= coef; w--) {
                    valorGrupo[b][w] = max(valorGrupo[b][w], valorGrupo[b][w - coef] + val);
                }
            }
        }

        int bits = 0;
        int tmp = W;
        while (tmp) {
            bits++;
            tmp >>= 1;
        }
        vector<vector<ll>> dp(bits + 1, vector<ll>(MAX_COEFF + 1, -1e18));
        dp[0][0] = 0;
        for (int b = 0; b < bits; b++) {
            for (int c = 0; c <= MAX_COEFF; c++) {
                if (dp[b][c] < 0) continue;
                for (int take = 0; take <= MAX_COEFF; take++) {
                    if (c >= take) {
                        int proximo = 2 * (c - take) + ((W >> b) & 1);
                        if (proximo <= MAX_COEFF) {
                            dp[b + 1][proximo] = max(dp[b + 1][proximo], dp[b][c] + valorGrupo[b][take]);
                        }
                    }
                }
            }
        }
        cout << dp[bits][1] << endl;
    }
    return 0;
}

P4138 [JOISC2014] 挂饰 Enunciado: Inicialmente há um gancho. Dados n itens, cada um com ganchos A_i e alegria B_i, selecione um subconjunto para pendurar maximizando a soma das alegrias. Cada item selecionado consome um gancho (exceto o primeiro) e fornece A_i ganchos adicionais. Abordagem: Ordenamos os itens por alegria decrescente. Tratamos o número de ganchos como o estado da DP, onde dp[i][j] é a alegria máxima usando os primeiros i itens com j ganchos restantes. A transição considera não selecionar o item ou selecioná-lo, atualizando o número de ganchos.

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

const ll INF = -1e18;

struct Item {
    int ganchos, alegria;
};

bool comparar(Item a, Item b) {
    return a.alegria > b.alegria;
}

int main() {
    int n;
    cin >> n;
    vector<Item> itens(n);
    for (int i = 0; i < n; i++) {
        cin >> itens[i].ganchos >> itens[i].alegria;
    }
    sort(itens.begin(), itens.end(), comparar);
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 2, INF));
    dp[0][1] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            if (dp[i][j] == INF) continue;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (j >= 1) {
                int novos_ganchos = j - 1 + itens[i].ganchos;
                if (novos_ganchos < 0) novos_ganchos = 0;
                if (novos_ganchos > n) novos_ganchos = n;
                dp[i + 1][novos_ganchos] = max(dp[i + 1][novos_ganchos], dp[i][j] + itens[i].alegria);
            }
        }
    }
    ll resposta = INF;
    for (int j = 0; j <= n; j++) {
        resposta = max(resposta, dp[n][j]);
    }
    cout << resposta << endl;
    return 0;
}