CFR 244 B. Undoubtedly Lucky Numbers ( Digit DP, Python deepcopy() )
題意:
給正整數 N,問有多少正整數不超過 N,在十進制下可以用不超過兩種數字表示。
資料規模:
N ≤ 1e9
解法:
dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴,已使用的數字是 ( j, k ),滿足 j < k,但特別的可以等於 10,代表不存在。
用 python 的編程瓶頸在於宣告多維陣列的部分,這裡是用 deepcopy()。
Makes me wonder whether there is any easier way to declare multidimensional arrays in python.....
from copy import deepcopy N = input() A = [ ord( N[ i ] ) - ord( '0' ) for i in range( len( N ) ) ] dp = [ 0, 0 ] dp = [ deepcopy( dp ) for i in range( 10 + 1 ) ] dp = [ deepcopy( dp ) for i in range( 10 + 1 ) ] dp = [ deepcopy( dp ) for i in range( len( A ) + 1 ) ] dp[ 0 ][ 10 ][ 10 ][ 0 ] = 1 for i in range( len( A ) ): for j in range( 10 + 1 ): for k in range( 10 + 1 ): for l in range( 2 ): lim = 9 if not l: lim = A[ i ] for d in range( lim + 1 ): if d == 0 and j == 10 and k == 10: dp[ i + 1 ][ 10 ][ 10 ][ 1 ] += dp[ i ][ j ][ k ][ l ] else: if j == 10 or j == d: dp[ i + 1 ][ d ][ k ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ] else: if k == 10: if d < j: dp[ i + 1 ][ d ][ j ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ] else: dp[ i + 1 ][ j ][ d ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ] else: if d != j and d != k: continue dp[ i + 1 ][ j ][ k ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ] ans = 0 for i in range( 10 ): for j in range( 10 + 1 ): for k in range( 2 ): ans += dp[ len( A ) ][ i ][ j ][ k ] print( ans )