ABC154-E (chiffre DP) en Python

problème

Comprenez et montrez ABC154-E!

Nombre total

Tout d'abord, le nombre total de nombres N ou moins est calculé à l'aide du chiffre DP. Considérez 314159. Par exemple, si vous avez choisi jusqu'à 313, tout nombre inférieur est autorisé. En revanche, si la règle est 314, seul 0 ou 1 est autorisé sous un. En d'autres termes, il est nécessaire d'avoir des informations sur le chiffre à décider et si moins de N est décidé par la méthode de décision. ** dp [i] [j]: déterminer jusqu'au i-ième chiffre, j = 1 s'il est confirmé inférieur à N, j = 0 ** s'il correspond à N Être déterminé. Puisque la valeur initiale correspond à N à ce stade en utilisant jusqu'au 0ème chiffre dp[0][0] = 1 Et. Après cela, le nombre de chiffres est augmenté, mais pour le chiffre suivant, le nombre qui correspond à N est toujours 1 (le même que le précédent), et le nombre inférieur à N est 0 pour celui qui est confirmé comme étant inférieur à N un auparavant. La formule de graduation est la suivante car elle est le produit de ~ 9 multiplié par 10 et celui égal au N précédent multiplié par 0 ~ le nombre de chiffres-1. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(str(N)[i - 1])

code

N = input()
m = len(N)
dp = [[0] * 2 for _ in range(m + 1)]
dp[0][0] = 1

for i in range(1, m + 1):
    dp[i][0] = dp[i - 1][0]
    dp[i][1] = dp[i - 1][1] * 10 + dp[i - 1][0] * int(N[i - 1])

ans = dp[m][0] + dp[m][1]

print(ans)

Nombre total de N ou moins, y compris K nombres non nuls

** dp [i] [j] [k]: ajout d'une condition pour inclure k nombres non nuls ** Soit l le nombre du i-ème chiffre dp[i][0][k] = dp[i - 1][0][k] * (l == 0),dp[i - 1][0][k - 1] * (l != 0) dp[i][1][k] = dp[i - 1][1][k] + dp[i - 1][1][k - 1] * 9 + dp[i - 1][0][k] * 1 * (l != 0) + dp[i - 1][0][k - 1] * (l - 1) * (l != 0) Je pense que ce sera le cas, mais s'il vous plaît dites-moi parce que cela semble être du gaspillage> <

Façon de penser

dp [i] [0] [k]: Si l est 0, alors k reste le même pour correspondre au nombre donné, donc dp [i -1] [0] [k], sinon Parfois, le nombre qui n'est pas 0 augmente de un, donc dp [i -1] [0] [k -1].

dp [i] [1] [k]: d'abord, à partir de dp [i -1] [1] [k], un chiffre suivant différent de zéro, dp [i -1] [1] [k -1] Le chiffre suivant est 9 de 1 à 9. Ensuite, si l n'est pas 0, dp [i -1] [0] [k] avec le chiffre suivant comme 0 devient dp [i -1] avec le chiffre suivant comme 1 ~ (l -1). ] [0] [k -1] transitions par l -1. (Cèdre inintelligible)

code

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

print(dp[m][0][K] + dp[m][1][K])

Épilogue

Veuillez me donner quelques conseils. .. .. .. Je répondrai à autant de questions que possible. .. .. ..

Les références

Introduction à Digit DP