首页 > 其他 > 详细

数位DP小结

时间:2018-07-21 00:31:19      阅读:200      评论:0      收藏:0      [点我收藏+]

1.简介

数位DP是用来解决一段区间内,存在多少个数满足某个数的性质的问题

题目中输入的数可能会爆int,一般为 0 < a、b < 2*10^9

数位DP中处理的是每一个数的位,而不是这个数的本身

也就是说1024,2024在后面三位在性质上是一样的,所以dp会保存这三位的状态

这样就节省了时间复杂度

一般来说,数位DP的时间复杂度位常数k*(dp数组的大小) 

2.数位DP状态的定义

数位DP的状态依赖于题目说需要求的数的性质

一般来说是dp[20][性质1][性质2]and so on。。。第一维空间保存数的位,第二维空间保存第一种性质and so on。。。。

例如:HDU2089《不要62》 题意是求在区间(a,b)中有多少不含62,或者4这种数

   DP状态定义为dp[20][2] 第一维空间表示数的位,第二维表示是否含有6,因为如果是否含有4直接判断就行,而含有62的时候就需要

    先保存前一个数是否是6,如果含有的话这一个数是否是2,如果是的话就不存这个数

  

 

。。。未完待续

 

数位DP小结

原文:https://www.cnblogs.com/buerdepepeqi/p/9344680.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!