数位dp – Tgotp-Blog

2147: Digit

看到题目首先想到了数位dp

观察发现,从低位向高位很好推.

令fijkg表示第i个位置,进位值为j 数位和为k 乘d后数位和为g得情况是否成立...

稍微算一算100 * 10 * 1000 * 1000肯定爆掉了...

考虑优化,令fijk表示能凑成进位值为i 数位和为j[......]

Read more

1833: [ZJOI2010]count 数字计数

数位dp

令f[i][j][k][e]代表f为 i 位,是否受该位限制,已有 k个 z 是否有前导零的方案数。

c++代码如下:

 

1026: [SCOI2009]windy数

bz蜜汁不接受math库?

数位dp入门题。巩固基础必备。

c++代码如下:

 

hdu 2089 不要62

题意:

统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

一开始写了一个预处理的版本,死活对不了,只好改成了dfs的,一开始还有理解问题,但是想通了就好了。

dp[i][0/1]表示第i位,上一位是否为6的方案数。

然后记忆化搜索,就这样。

数位dp模板题[......]

Read more