ABC154-E (Ziffer DP) in Python

Problem

ABC154-E verstehen und zeigen!

Gesamtzahl

Zunächst wird die Gesamtzahl der Zahlen N oder weniger unter Verwendung der Ziffer DP berechnet. Betrachten Sie 314159. Wenn Sie sich beispielsweise für bis zu 313 entschieden haben, ist eine beliebige Zahl darunter zulässig. Wenn andererseits die Regel 314 ist, ist unten nur 0 oder 1 zulässig. Mit anderen Worten, es ist erforderlich, Informationen darüber zu haben, welche Ziffer zu entscheiden ist und ob weniger als N durch die Entscheidungsmethode entschieden wird. ** dp [i] [j]: Bestimmen Sie bis zur i-ten Ziffer, j = 1, wenn weniger als N bestätigt wird, j = 0 **, wenn es mit N übereinstimmt Bestimmt werden. Da der Anfangswert an dieser Stelle mit N bis zur 0. Ziffer übereinstimmt dp[0][0] = 1 Und. Danach wird die Anzahl der Ziffern erhöht, aber für die nächste Ziffer ist die Zahl, die mit N übereinstimmt, immer 1 (dieselbe wie die vorherige), und die Zahl kleiner als N ist 0 für diejenige, von der bestätigt wurde, dass sie zuvor kleiner als N ist. Die Graduierungsformel lautet wie folgt, da es sich um das Produkt von ~ 9 multipliziert mit 10 und dem Produkt handelt, das dem vorherigen N multipliziert mit 0 ~ der Anzahl der Ziffern-1 entspricht. 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)

Gesamtzahl von N oder weniger einschließlich K Nicht-Null-Zahlen

** dp [i] [j] [k]: Bedingung hinzugefügt, um k Zahlen ungleich Null einzuschließen ** Sei l die Zahl in der i-ten Ziffer 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) Ich denke es wird sein, aber bitte sag es mir, weil es verschwenderisch zu sein scheint> <

Denkweise

dp [i] [0] [k]: Wenn l 0 ist, bleibt k gleich, um mit der angegebenen Zahl übereinzustimmen, andernfalls dp [i -1] [0] [k] Manchmal erhöht sich die Zahl ungleich Null um eins, also dp [i -1] [0] [k -1].

dp [i] [1] [k]: Zuerst von dp [i -1] [1] [k] eine nächste Ziffer ungleich Null, dp [i -1] [1] [k -1] Die nächste Ziffer ist 9 von 1 bis 9. Wenn l nicht 0 ist, wird dp [i -1] [0] [k] mit der nächsten Ziffer als 0 zu dp [i -1] mit der nächsten Ziffer als 1 ~ (l -1). ] [0] [k -1] Übergänge um l -1. (Unverständliche Zeder)

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])

Nachwort

Bitte geben Sie mir einen Rat. .. .. .. Ich werde so viele Fragen wie möglich beantworten. .. .. ..

Verweise

Einführung in Digit DP