首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

HDU 2089 不要 62:數位 DP 統計不含 4 和 62 的數字個數

     編輯:關於C++

題目大意

多組查詢,每組給定區間 [s, e],求區間內不含數字 4、也不含連續子串 "62" 的整數個數。s, e ≤ 10^6?實際上 e 可達 10^9,需數位 DP。

DP 定義

dp[pos][prev]:從高位到低位處理到第 pos 位(0 為最低位),前一位數字為 prev(0~9,10 表示無前一位/前導零),滿足條件的方案數。
狀態轉移:枚舉當前位 dig (0~9),若 dig==4 跳過;若 prev==6 && dig==2 跳過;否則累加 dp[pos-1][dig]。

預處理打表

因無上界限制,可預計算 dp[len][firstDigit]:長度為 len、最高位為 firstDigit 的合法數個數。
dp[0][0]=1;
dp[i][j] = Σ dp[i-1][k] (k≠4, 且不滿足 j==6&&k==2)。

查詢函數 solve(x)

返回 [0, x] 合法數個數。將 x 分解為數位數組 digit[](高位在前)。從高位向低位枚舉:
對第 i 位,枚舉 d = 0 ~ digit[i]-1,若合法則累加 dp[i][d]。
若 digit[i] 本身非法(==4 或 前位==6且本位==2),中斷。
最後返回累加和。

答案 = solve(e) - solve(s-1)。

參考代碼(C++)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved