鞠古香 发表于 2025-7-15 19:36:52

关于数位dp

本来是8个月前答应写的，咕咕了240天，汗
数位dp

定义：from-OI Wiki


说点人话：

当一道关于特定数字计数的问题出现，值域范围到达\(10^{18}\),可以通过枚举每个数位上的数, 递推/搜索 出答案
小思想:关于统计区间\(\)之间数的数量

前缀和:\(sum=sum-sum\)
具体例题

1. P2602 数字计数

可以发现,如果直接枚举数字,会炸掉,联想一下会枚举的数字

[*]11111111
[*]......
[*]21111111
[*]''''''
[*]31111111
[*]......
发现重合部分好多,可不可以避免重合呢?
直接告诉你 : 爆搜+剪枝
(比如)搜到亿位时,发现后面的数字出现次数相当,直接返回搜过的值
给出基本代码并讲解

int dfs(int pos,bool limit,int sum,bool lead0,int d){        int res=0;        if(!pos) return sum;        if(!limit&&dp!=-1) return dp;        int up=limit?a:9;        for(int i=0;i

呼延含玉 发表于 2025-10-9 11:33:11

用心讨论，共获提升！

荆邦 发表于 2025-10-29 04:11:40

这个有用。

计海龄 发表于 2025-11-4 03:46:24

谢谢分享，试用一下

俏挺喳 发表于 2025-11-25 15:51:52

感谢分享

拙因 发表于 2025-12-14 14:03:55

这个好，看起来很实用

鞣谘坡 发表于 2026-1-9 02:47:23

新版吗？好像是停更了吧。

铵滔 发表于 2026-1-17 19:24:59

新版吗？好像是停更了吧。

煞赶峙 发表于 2026-1-18 16:36:18

谢谢分享，试用一下

怀陶宁 发表于 2026-1-21 04:34:43

分享、互助 让互联网精神温暖你我

但婆 发表于 2026-1-21 10:26:08

热心回复！

时思美 发表于 2026-1-21 19:09:54

东西不错很实用谢谢分享

表弊捞 发表于 2026-1-23 04:54:26

新版吗？好像是停更了吧。

讥慰捷 发表于 2026-1-29 05:40:35

yyds。多谢分享

埤兆 发表于 2026-1-30 03:28:55

热心回复！

骆贵 发表于 2026-2-5 04:14:34

新版吗？好像是停更了吧。

溧久苟 发表于 2026-2-9 09:53:51

不错，里面软件多更新就更好了

纪音悦 发表于 2026-2-9 13:54:16

这个有用。

空娅芬 发表于 2026-2-10 02:24:11

感谢发布原创作品，程序园因你更精彩

讣丢 发表于 2026-2-10 04:15:51

这个好，看起来很实用
页: [1] 2
查看完整版本: 关于数位dp