Mathison
2018-10-10 07:31:43
数位dp就是套模板 ——lwz dalao
(数位dp确实可以套模板,但笔者建议还是要理解这个过程,这样才能灵活变化)
数位dp一直以来是dp家族里比较冷门的一种,但一旦考察不会数位dp靠暴力很难骗分
今天我们就来分析一下数位dp的全过程
首先我们要清楚数位dp解决的是什么问题:
由于数是按位dp,数的大小对复杂度的影响很小
这里我们使用记忆化搜索实现数位dp。本质上记搜其实就是dp,下文会重点介绍dp值的使用和记录
从起点向下搜索,到最底层得到方案数,一层一层向上返回答案并累加,最后从搜索起点得到最终答案。
对于
如果理解了上述过程,我们需要考虑的就是怎样判断现在在哪一层,怎样判断当前的状态——这就需要我们传进一些参量。
首先是数位dp基本的量数字位数
我们还需要一个判断判断前导0的标记
由于数位dp解决的大多是数字组成问题,所以经常要比较当前位和前一位或前几位的关系(根据题意而定),所以一般在dfs()中也要记录前一位或前几位数
除此之外还可以传进更多参量以区分状态,视题意而定。
数位dp的状态能记录的最好都记录上 ——lwz dalao
由于我们要搜的数可能很长,所以我们的直接最高位搜起
举个例子:假如我们要从
显然
但是我们发现右端点
因此我们搜索的起点是
而这种情况下如果我们直接找相邻位相等则
所以我们要加一个前导0标记
当然前导
我们知道在搜索的数位搜索范围可能发生变化;
举个例子:我们在搜索
为了分清这两种情况,我们引入了
我们设这一位的标记为
最后我们考虑dp数组下标记录的值
本文介绍数位dp是在记忆化搜索的框架下进行的,每当找到一种情况我们就可以这种情况记录下来,等到搜到后面遇到相同的情况时直接使用当前记录的值。
dp数组的下标表示的是一种状态,只要当前的状态和之前搜过的某个状态完全一样,我们就可以直接返回原来已经记录下来的dp值。
再举个例子
假如我们找
假如当我们搜到
当我们继续搜到
注意,我们返回的dp值必须和当前处于完全一样的状态,这就是为什么dp数组下标要记录
最重要的来了————————————————————
接着上面的例子,范围
如果我们搜到了
答案是否定的
我们发现,这个状态的dp值被记录时,当前位也就是第
当前位的取值范围为什么会和原来不一样呢?
如果你联想到了之前所讲的知识,你会发现:现在的
因此我们可以得到一个结论:当
类似上述的分析过程,我们也可以得出:当
p.s.当然没有这么绝对的说……因题而异的说……
以上就是计划搜索的完整步骤。
附图:
ll dfs(int pos,int pre,int st,……,int lead,int limit)//记搜
{
if(pos>len) return st;//剪枝
if((dp[pos][pre][st]……[……]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st]……[……];//记录当前值
ll ret=0;//暂时记录当前方案数
int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值
for(int i=0;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=0;
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,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-1));//[l,r](l!=0)
else printf("%lld",part(r)-part(l));//从0开始要特判
}
return 0;
}
注: 推荐此题的原因是这道题涉及到的需要记录的量较多,比较典型,如果觉得比较难理解也没关系,先看下面的例题推荐
【题意简述】
定义一个正整数的价值是把这个数的十进制写出来之后,最长的等差子串的长度。
求
【分析】
这道题很显然是一道数位dp,那么我们应该怎么样设计状态和转移呢?
数位位置,前一位数,等差数列共差是一定要记录的
我们还要把当前最大价值和整个数最大值也作为状态
dp过程见代码注释(数位dp主要还是套板子呀)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,len,a[20];
ll l,r,dp[20][15][25][25][20];
ll dfs(int pos,int pre,ll st,ll sum,int d,int lead,int limit)
//pos搜到的位置
//pre前一位数
//st当前公差最大差值
//sum整个数字的最大价值
//d共差
//lead判断是否有前导0
//limit判断是否有最高位限制
{
if(pos>len) return sum;//dp结束
//记录状态(计划搜索)
//注意d有负数,最小可以到-9,所以记录时数组下标是d+10
if((dp[pos][pre][st][sum][d+10]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st][sum][d+10];
ll ret=0;
int res=limit?a[len-pos+1]:9;//最高位最大值
for(int i=0;i<=res;i++)
{
//有前导0且这位也是前导0,一切不变只有位数变化
if((!i)&&lead) ret+=dfs(pos+1,0,0,0,-38,1,limit&&(i==res));
//有前导0但这位不是前导0(这位是数字的最高位)开始有前一位,一个数形成等差数列
else if(i&&lead) ret+=dfs(pos+1,i,1,1,-38,0,limit&&(i==res));
//之前刚搜到1位还没有共差,两位数形成等差数列,记录共差
else if(d<-9) ret+=dfs(pos+1,i,2ll,2ll,i-pre,0,limit&&(i==res));
//搜到2位以后,共差若与前两位相同当前等差数列长度增加,若公差变化则更新整个数字的最大价值,等差数列长度又变为2
else if(d>=-9) ret+=dfs(pos+1,i,(i-pre==d)?st+1:2,max(sum,(i-pre==d)?st+1:2),(i-pre==d)?d:i-pre,0,limit&&(i==res));
}
//没有前导0和最高限制时可以直接记录当前dp值以便下次搜到同样的情况可以直接使用。
return (!limit&&!lead)?dp[pos][pre][st][sum][d+10]=ret:ret;
}
ll part(ll x)
{
len=0;
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,sizeof dp);
return dfs(1,0,0,0,-38,1,1);//-38是随便赋的其实赋成-10就行了……
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&l,&r);
//l是0的时候要特别注意!
printf("%lld\n",l?(part(r)-part(l-1)):(part(r)-part(l)+1));
}
return 0;
}
[HDU2089]不要62
入门题,如果上面的例题没看懂可以先尝试一下这道题,如果上面的例题理解了这题可以秒切
P2657 [SCOI2009]windy数
P2602 [ZJOI2010]数字计数
这两题是数位dp题目里的基础题,多体会上述的讲解就能够顺利地想出解法(实在不行还可以背板子的吧)
P3413 萌数
这道题是笔者接触数位dp的第一题,当时学长讲完之后还有点懵,现在发现不是特别难的题目,还是比较套路的
P4127 [AHOI2009]同类分布
P4317 花神的数论题
相比前面,这道题就显得灵活一些,可能在统计答案的方法上有一些变化,但相信当你做完上面的题之后,这两道题也不在话下!
当然也有些题看起来不是数位dp,但是可能依靠一些数论知识把问题转化成一道数位dp题(比如一些数字本身的性质转化成数字组成的特点),这里就不再过多赘述。
数位dp虽然大多在套模板,但是里面的判断和细节还是很多的,多写几道数位dp之后才能发现其中的规律,完全将其掌握。
本文是笔者听过了两位dalao的讲解后撰写而成
初识数位dp:学长Vergil 【LVYOUYW】
知识巩固:dalao lwz 【lwz2002】