Programação Dinâmica com dígitos [Pt 3]: Editorial

Vamos aqui abordar dois problemas que são bons exemplos de PD com dígitos e não são fáceis:

Spoj NUMTSN: 369 Numbers (link para o problema)
Codeforces 2015-2016 Petrozavodsk Winter Training Camp: Maximum Product (link para o problema)

No primeiro problema, queremos contar quantos números 369 existem entre A e B inclusivo. Esse números tem:

• pelo menos um dígito 3;
• o mesmo número de dígitos 3, 6 e 9.

O problema é que os números vão até 10^50. O problema é muito parecido com o da soma da parte 1, a diferença é que, ao invés de olhar a soma, precisamos olhar o número de dígitos 3, 6 e 9. Podemos computar de 0 a B e depois de 0 a A e subtrair o resultado (precisamos checar também o caso A, já que B-A não engloba esse caso).

int dp[MAXN][MAXN][MAXN][MAXN]; // Matriz preenchida com -1 inicialmente

int calc(int digit, int t, int s, int n) {
    if (digit == 0) {
        return (t >= 1 && s == t && s == n) ? 1 : 0;
    }
    int& ans = dp[digit][t][s][n];
    if (ans >= 0) return ans;
 
    ans = 0;
    for (int i = 0; i <= 9; i++) {
        // Ve o que acontece quando adiciona o digito i
        // t, s, n somam +1 se i for 3, 6 ou 9
        ans += calc(digit-1, t + (i == 3), s + (i == 6), n + (i == 9));
        ans %= MOD;
    }
    return ans;
}

int compute(const char *numero, int n) {
    int ans = 0;
    // Numero acumulado de tres, seis e noves
    int three = 0, six = 0, nine = 0;

    for (int i = 0; i < n; i++) {
        int digit = numero[i] - '0';
        for (int d = 0; d < digit; d++) {
            ans += calc(n-i-1, three + (d == 3), six + (d == 6), nine + (d == 9));
            ans %= MOD;
        }
        three += (digit == 3); six += (digit == 6); nine += (digit == 9);
    }
    return ans;
}

O segundo problema é um pouco mais difícil, queremos saber o número entre A e B cujo o produto dos dígitos é o máximo possível -- por exemplo, 319 tem produto 3*1*9 = 27, e 101 tem produto 1*0*1 = 0. Pra isso, primeiro computamos o produto máximo, redefinindo a nossa PD. Uma ressalva é que zeros à esquerda do primeiro dígito não contam, por isso precisamos armazenar na PD se o primeiro dígito já foi usado (se não, podemos colocar 0 sem multiplicar o produto por 0).

typedef long long ll;
ll dp[MAXN][2][2][2]; // Matriz preenchida com -1 inicialmente

ll calc(int d, int moreA, int lessB, int firstDigit) {
    if (d == 0) return 1LL;
    ll& ans = dp[d][moreA][lessB][firstDigit];
    if (ans >= 0) return ans;

    int sup = lessB ? 9 : (superior[d] - '0'); // d-esimo digito do teto
    int inf = moreA ? 0 : (inferior[d] - '0'); // d-esimo digito do piso
 
    ans = 0;
    for (int i = inf; i <= sup; i++) {
        ll mult = 1;
        // Se o primeiro digito nao foi usado e i == 0, entao ignoramos a multiplicacao
        if (firstDigit == 1 || (i > 0)) mult = i;

        // Resposta eh o maximo entre valores anteriores e o obtido adicionando i
        ans = max(ans, mult*calc(d-1, moreA | (i > inf), lessB | (i < sup),
                 firstDigit | (i > 0)));
    }
    return ans;
}

Para reconstruir o número, precisamos repetir as escolhas que maximizam esse produto. Portanto, testamos o que acontece quando adicionamos um número: se o valor encontrado for igual ao do máximo produto, então mantemos, e fazemos isso para cada um dos dígitos. O código fica parecido com o que está abaixo.

void reconstruct(int d, int moreA, int lessB, int firstDigit) {
    if (d == 0) return;

    int sup = lessB ? 9 : (superior[d] - '0'); // d-esimo digito do teto
    int inf = moreA ? 0 : (inferior[d] - '0'); // d-esimo digito do piso
 
    for (int i = inf; i <= sup; i++) {
        ll mult = 1;
        if (firstDigit == 1 || (i > 0)) mult = i;
        ll val = mult*calc(d-1, moreA | (i > minV), lessB | (i < maxV),
                           firstDigit | (i > 0));

        // Se o valor obtido colocando i for igual ao maximo, adicionamos i
        if (val == calc(d, moreA, lessB, first)) {
            if (nonZero || (i > 0)) cout << i; // Printa i
            // Reconstruir o resto dos digitos
            reconstruct(d-1, moreA | (i > inf), lessB | (i < sup),
                        firstDigit | (i > 0));
            return;
        }
    }
}

Existem vários jeitos de resolver problemas com DP com dígitos, essa é uma das opções! A complexidade é (tamanho da matriz dp) x (10 dígitos ou mais), pois cada elemento da matriz é computado uma única vez e depende de 10 opções. Outras são válidas e podem ser até mais rápidas ou mais lentas.