数位DP 学习笔记
前言:鸣谢https://www.luogu.com.cn/blog/virus2017/shuweidp。感谢大佬orz
-----------------------------
【引入】
首先要明白数位DP解决的是什么问题。
问题:求出在$[L,R]$内满足条件$f(i)$的$i$的个数。$f(i)$一般不与数的大小有关,而是与数的组成有关。(数的大小对复杂度的影响很小)
【设计搜索】
数位DP一般都用记忆化搜索来实现。
一、记搜过程
从起点向下搜索,到最底层得到方案数,一层一层向上返回答案并累加,最后从搜索起点得到最终答案。
对于$[l,r]$区间问题,我们一般把他转化为两次数位dp,即找$[0,r]$和$[0,l-1]$两段,再将结果相减就得到了我们需要的$[l,r]$。
二、状态设计
问:$dfs$函数需要哪些参量?
1.首先是记录位置的$pos$,记录答案的$st$,最高位限制$limit$。
2.判断前导0的标记$lead$。
3.因为数位DP一般与数的组成有关,所以当前位可能要与前几位进行比较。所以要设置$pre$用来表示前几位。
4.有可能会有其他参量,依据题意而定。
数位DP中能记录的状态最好都记录下来。
【细节分析】
一、前导0标记$lead$
例如,寻找$[0,1000]$内任意相邻两数相等的数。
由题意得:$111,222,888$等都符合题意。但右端点$1000$是四位数,因此我们要从$0000$开始搜,那么$0000$符合题意但$0111,0222,0888$都不符合题意了。
所以我们要加一个前导0标记。
1.如果当前位是0并且前导0标记$lead$是1,那么$pos+1$继续深搜。
2.如果前导0标记是1但当前位不是0,那么此位作为最高位继续深搜(注意此时传递参量可能发生变化)。
当然有时候前导0是不需要记录的,因题而异。如果是研究数字组成的话一般就不用标记前导0。
二、最高位标记$limit$
例如,在搜索$[0,555]$时,显然最高位搜索范围是$[0,5]$,而后面的搜索根据最高位搜索发生变化:
1.当最高位是$[1,4]$时,显然后面范围是$[0,9]$。
2.当最高位是$5$时,第二位的范围是$[0,5]$。
为了区分两种情况:我们引入$limit$标记:
1.当前位$limit=1$且取到最高位时,下一位$limit=1$。
2.当前位$limit=1$但没有取到最高位时,下一位$limit=0$。
3.当前位$limit=0$,则下一位$limit=0$。
我们设这一位标记是$limit$,能取到的最高位是$res$,那么下一位的标记就是(i==res)$$limit。
三、DP值的记录与使用
DP数组下标记录的是状态,所以如果当前状态和之前搜过的状态完全一样,我们就可以不用继续深搜,直接返回值即可。
举个例子:
假如我们搜索$[0,123456]$中符合条件的数。
现在搜到了$1000??$,我们记录下来了当前位是第五位,且前一位是0的值。
下一次,我们搜到了$1010??$,我们可以不用再深搜,直接返回之前搜过的值即可。
但是!!!!!
假如现在我们搜到了$1234??$我们可不可以返回当前位是第五位,且前一位是4的值?
当然不行。因为之前的值第五位取值范围是$[0,9]$,而现在取值范围是$[0,5]$,答案数显然不一样,不能混为一谈。
联系之前的知识,我们很容易想到:此时$limit=1$。
因此我们得到一个结论:当$limit=1$时,不能记录和取用DP值。
同样,当$lead=1$时,不能记录和取用DP值。
当然,这还是要看具体题意的。在使用DP数组的过程中也可以把所有状态记录下来,就没有那么多麻烦事了……
【模板】
ll dfs(int pos,int pre,int st,……,int lead,int limit)//记搜
{
if(pos>len) return st;//剪枝
if((dp[pos][pre][st]……[……]!=-&&(!limit)&&(!lead))) return dp[pos][pre][st]……[……];//记录当前值
ll ret=;//暂时记录当前方案数
int res=limit?a[len-pos+]:;//res当前位能取到的最大值
for(int i=;i<=res;i++)
{
//有前导0并且当前位也是前导0
if((!i)&&lead) ret+=dfs(……,……,……,i==res&&limit);
//有前导0但当前位不是前导0,当前位就是最高位
else if(i&&lead) ret+=dfs(……,……,……,i==res&&limit);
else if(根据题意而定的判断) ret+=dfs(……,……,……,i==res&&limit);
}
if(!limit&&!lead) dp[pos][pre][st]……[……]=ret;//当前状态方案数记录
return ret;
}
ll part(ll x)//把数按位拆分
{
len=;
while(x) a[++len]=x%,x/=;
memset(dp,-,sizeof dp);//初始化-1(因为有可能某些情况下的方案数是0)
return dfs(……,……,……,……);//进入记搜
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&l,&r);
if(l) printf("%lld",part(r)-part(l-));//[l,r](l!=0)
else printf("%lld",part(r)-part(l));//从0开始要特判
}
return ;
}
【题目推荐】
题目难度按照次序。T5比较难,思维题。
-----------------------------------------
后记:我再也不说数位DP是板子题这种话了QAQ
最新文章
- 何解決 LinqToExcel 發生「無法載入檔案或組件」問題何解決 LinqToExcel 發生「無法載入檔案或組件」問題
- thinkphp添加空数据的解决办法
- Sql Practice 2
- jQuery插件之jqzoom
- Ubuntu 32下Android NDK+NEON的配置过程及简单使用举例
- PHP class which generates PDF files from UTF-8 encoded HTML
- C#中的原子操作Interlocked,你真的了解吗?
- 慢查询日志分析(mysql)
- 如何用cmake编译
- 添加PROPAGATION_REQUIRES_NEW 事务没有产生作用
- oninput和onchange的区别
- CF 545C
- TLS握手、中断恢复与证书中心的原因
- BZOJ2325 [ZJOI2011]道馆之战 树链剖分 线段树
- kepware http接口 GO语言开发
- XFire搭建WebService和客户端访问程序
- CSS继承元素属性
- C#画图消除锯齿
- ASP.NET WebAPI2 发布之后404 Not Found
- 【甘道夫】Eclipse+Maven搭建HBase开发环境及HBaseDAO代码演示样例
热门文章
- Cypress系列(13)- 详细介绍 Cypress Test Runner
- spring cloud gateway 限流做法
- JVM 学习笔记(五)
- typeError:The value of a feed cannot be a tf.Tensor object.Acceptable feed values include Python scalars,strings,lists.numpy ndarrays,or TensorHandles.For reference.the tensor object was Tensor...
- 网页排名算法PagaRank
- TCP 和 UDP,哪个更胜一筹
- 题解 UVA1193 Radar Installation
- 6.ALOHA协议
- ES6面试
- javascript中的设计模式之发布-订阅模式