数位DP
•问题：在给定区间[A,B]内，找满足要求的数。
•要求一般和数大小无关，而与数的组成有关
•例如，递增的，1234,2579…
• 双峰的，19280,26193…
• 含49的，49, 149, 1492…
• 整除13的，26, 39…
•麻烦在于，规模大，位数>100，不能枚举。
•并且区间往往不是整百整千，需要小心处理边界
•注意
–记忆化搜索思路清晰
–开适当空间（能省则省）
–寻找合适的状态，简化计算量
例hdu3886
•题目大意：给一定区间[A,B]，一串由/,\,-组成的符号串。求满足符号串的数字个数。
•/表示数字从左到右递增
•\表示数字从左到右递减
•-表示数字从左到右相等
•例如:
•/-\
•1221,123455543
•数据规模:
•A,B<=10^100
分析
F(A,B) = F(B,0)-F(A-1,0) //区间[A,B]中符合要求的数量 = 区间[0,B]的 - 区间[0,A-1]的
因此只要考虑区间[0,num]的情况就好了
暴力+存储= 记忆化搜索
•暴力
•暴力枚举每一位(0..9),注意区间边界;与符号的匹配。
•递归函数为 int dfs(i,j,k,flag)
•表示 枚举第i位的数，匹配str[j],前一位是k，是否达到上限(flag=true,false)， 返回此时符合要求的数量
•注意边界，如果达到了上限则只能枚举0..num[i]，否则可以枚举0..9
例如 num[] = 157, 枚举到14*时，个位可以为0..9，但是枚举到15*时，个位只能为0..7
•存储
•dfs(i,j,k,flag)
•设状态与递归参数一致f[i][j][k][flag]，表示当枚举到第i位的数，匹配str[j],前一位是k，是否达到上限(flag=true,false)时，满足要求的数字个数。
•dfs的过程，相当于在填充f，f的空间O(100*10*10*2)，则dfs的时间O(20000)
实现
•1.空间优化，只需记录flag=false时的值。因为flag=true的值只会计算一次，不是冗余计算，不用记录。
–（不一定要开和参数一样的数组，适当变换下，分成几种情况开多个数组，可以节省下内存）
•2.前导0不算数，不能和符号串匹配。特判下即可
–如,-/,0003(X),0113
•3.1234 匹配//，会被算成俩个。特判下即可
•4. 个位放在f[0][…]，或者说157要存成num[] = 751，且只记录flag=false的值时，f与数A,B无关！可以反复利用，对于有多组输入样例的问题速度更快
其他类型
•整除13
•dfs(i, m,flag)
•枚举第i位数，前面枚举出的数模13的余数m，是否到达上限flag
•整除自身各位数CF55D
•dfs(i, m,l, flag)
•枚举第i位数，前面枚举出的数模LCM(0..9)，LCM(前面枚举出的数)，是否达到上限
•包含”49”
•dfs(i, k,find, flag)
•枚举第i位数，前一位是k，是否已包含”49”(find=true,false)，是否达到上限
•分类讨论：前一位是否为4，当前是否已包含“49”
部分解题报告：（习惯写在代码末尾...）
POJ 3252 Round Number
HDU 3709 Balanced Number
HDU 3652 B-number
codeforce 55D Beautiful numbers
写到后来发现这已经成了模板题了，遇到问题，不用想太仔细，直接套上模板，快速、简单、准确。
Read full article from 【专题】数位DP(按位DP) - cmonkey - 博客频道 - CSDN.NET
No comments:
Post a Comment