关于数位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
页:
[1]