POJ 3286 How many 0's?(數位dp)
題意
輸入n,m,求n~m范圍內的所有數字中,0出現的總數是多少。
思路
用2034做個例子。
枚舉0在個十百千位上出現的次數
個:個位為0時,後面不需要考慮,只需考慮前面,因為0比4小,所以前面即使取到最大也不會過限,所以前面可以是1~203(因為當前位是0,所以前面不能是0)。一共203種。
十:十位為0時,前面取1~20,後面取0~9。一共123*10種。
百:百位為0時,因為0與當前位上限0相等,所以前面取1時,後面可以取0~99,前面取2時,後面只能取0~34。一共1*100+35種。
千位顯然不能為0,所以總數為0。
把上述思想轉化為代碼即可。
代碼
#include
#include
#include
#include
#include
#include
#include
#include