数位DP总结+模板
简介:
数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位……数的每一位就是数位啦!
之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。
一种新的枚举方式:
两种不同的枚举:对于一个求区间[le,ri]满足条件数的个数,最简单的暴力枚举不方便记忆化,或者说根本无状态可言。
新的枚举:控制上界枚举,从最高位开始往下枚举,例如:ri=213,那么我们从百位开始枚举:百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看)
然后每一位枚举都不能让枚举的这个数超过上界213(下界就是0或者1,这个次要),当百位枚举了1,那么十位枚举就是从0到9,因为百位1已经比上界2小了,后面数位枚举什么都不可能超过上界。所以问题就在于:当高位枚举刚好达到上界是,那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2,那么十位的枚举情况就是0到1,如果前两位枚举了21,最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。
最后一个问题:最高位枚举0:百位枚举0,相当于此时我枚举的这个数最多是两位数,如果十位继续枚举0,那么我枚举的就是以为数咯,因为我们要枚举的是小于等于ri的所以数,当然不能少了位数比ri小的咯!(这样枚举是为了无遗漏的枚举,不过可能会带来一个问题,就是前导零的问题,模板里用lead变量表示,不过这个不是每个题目都是会有影响的,可能前导零不会影响我们计数,具体要看题目)
由于这种新的枚举只控制了上界所以我们的Main函数总是这样:
| int main() { long long le,ri; while(~scanf("%lld%lld",&le,&ri)) printf("%lld\n",solve(ri)-solve(le-1)); }
|
数位DP板子+详解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| typedef long long ll; int a[20]; ll dp[20][state]; ll dfs(int pos,,bool lead,bool limit) { if(pos==-1) return 1; if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) { if() ... else if()... ans+=dfs(pos-1,,lead && i==0,limit && i==a[pos])
} if(!limit && !lead) dp[pos][state]=ans; return ans; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,,true,true); } int main() { ll le,ri; while(~scanf("%lld%lld",&le,&ri)) { printf("%lld\n",solve(ri)-solve(le-1)); } }
|
例题:
HDU2089-不要62:
就是数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。
$dp[pos][sta]$表示当前第$pos$位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<bits/stdc++.h> using namespace std; typedef long long ll;
int a[20]; int dp[20][2]; int dfs(int pos,int pre,int state,bool limit) { if(pos==-1) return 1; if(!limit&&dp[pos][state]!=-1) return dp[pos][state]; int up=limit?a[pos]:9; int tep=0; for(int i=0;i<=up;i++) { if(pre==6&&i==2) continue; if(i==4) continue; tep+=dfs(pos-1,i ,i==6,limit&&i==a[pos]); } if(!limit) dp[pos][state]=tep; return tep; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x=x/10; } return dfs(pos-1,-1,0,true); } int main() { int l,r; while(scanf("%d%d",&l,&r)!=EOF&&(l||r)) { memset(dp,-1,sizeof dp); printf("%d\n",solve(r)-solve(l-1)); } return 0; }
|
HDU3555-Bomb:
一样,这个是不要49
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #include<bits/stdc++.h> using namespace std; typedef long long ll;
int a[20]; ll dp[20][2]; ll dfs(int pos,int pre,int state,bool limit) { if(pos==-1) return 1; if(!limit&&dp[pos][state]!=-1) return dp[pos][state]; int up=limit?a[pos]:9; ll tep=0; for(int i=0;i<=up;i++) { if(pre==4&&i==9) continue; tep+=dfs(pos-1,i ,i==4,limit&&i==a[pos]); } if(!limit) dp[pos][state]=tep; return tep; } ll solve(ll x) { int pos=0; while(x) { a[pos++]=x%10; x=x/10; } return dfs(pos-1,-1,0,true); } int main() { int T; scanf("%d",&T); memset(dp,-1,sizeof dp); while(T--) { ll x; scanf("%lld",&x); printf("%lld\n",x-solve(x)+1); } return 0; }
|
一些优化技巧:
第一:memset(dp,-1,sizeof dp);放在多组数据外面。
这一点是一个数位特点,使用的条件是:约束条件是每个数自身的属性,而与输入无关。
具体的:上一题不要62和4,这个约束对每一个数都是确定的,就是说任意一个数满不满足这个约束都是确定,比如444这个数,它不满足约束条件,不管你输入的区间是多少你都无法改变这个数不满足约束这个事实,这就是数自身的属性(我们每组数据只是在区间计数而已,只能说你输入的区间不包含444的话,我们就不把它统计在内,而无法改变任何事实)。
由此,我们保存的状态就可以一直用(注意还有要limit,不同区间是会影响数位在有限制条件下的上限的)
这点优化就不给具体题目了,这个还有进一步的扩展。不过说几个我遇到的简单的约束:
1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态,即dp[pos][sum]这里10 是与多组无关的,所以可以memset优化,不过注意如果题目的模是输入的话那就不能这样了。
2.求二进制1的数量与0的数量相等的个数,这个也是数自身的属性。
待补技巧:
1.HDU 4734 所用到的相减技巧
2.HDU 3709 这题就是要枚举中轴,然后数位dp