首先，我们要看出来这是一道数位DP题。。。
- 有上下界l,r;
- 只与数字的排列有关，与数字大小无关。
- 对于数字之间有诸多限制。
- 一般范围是在18位左右，此题11位，显然可以。
所以，FYJ说这是一道裸题。(Orz)
然后就很套路了。
在此先附一个数位模板，基本上大部分数位DP都是这个框架。（转载自某大佬blog，我觉得他应该不会和蒟蒻计较的。QwQ）
我在他的模板的基础上按照自己的习惯改了一下下...(建议看一看我的，我加了自己的补充。
#include<iostream> #include<stdio.h> #include<cstring> #define LL long long using namespace std; LL dp[11][11][11][2][2][2]; int a[11];int cnt; inline LL calc(int pos,int llast,int last,bool if4,bool if8,bool if3,bool head,bool limit){ if(pos==-1) return if3?1:0;//如果出现过连续三个相同的数，才符合条件。 if(!limit && !head && last!=-1 && llast!=-1 && dp[pos][llast][last][if4][if8][if3]!=-1) return dp[pos][llast][last][if4][if8][if3]; int up=limit?a[pos]:9;//上限。 int down=head?1:0;//下限。 LL tmp=0; for(int i=down;i<=up;++i){ if(if4 && i==8) continue;//有4不能有8. if(if8 && i==4) continue;//有8不能有4. tmp+=calc(pos-1,last,i,if4||(i==4),if8||(i==8),if3||(llast==last&&last==i),0,limit && i==a[pos]); //传递条件就好啦。 } if(!limit && !head && last!=-1 && llast!=-1) dp[pos][llast][last][if4][if8][if3]=tmp; return tmp; } inline LL devide(LL x){ cnt=-1; memset(a,0,sizeof a); while(x){ a[++cnt]=x%10; x/=10; } return cnt!=10?0:calc(cnt,-1,-1,0,0,0,1,1);//不足11位返回零就好啦。 //不要说不存在这种情况。 //因为我们传的是l-1。所以l=100 0000 0000 时，l-1=99 9999 9999 辣。 } int main(){ LL l,r; cin>>l>>r; memset(dp,-1,sizeof dp); cout<<devide(r)-devide(l-1); return 0; }
可能是我太弱的原因，我感觉数位dp就是记忆化搜索嘛。。。
不过话说dp的本质就是把不同的状态用同一种状态表示，方便转移。
那么对于这道题，需要注意的状态如下：
- 不能同时出现4和8,于是就多了两个bool型, bool if4,bool if8,表示4,8是否出现过。
- 要有三个连续的，所以就多了,int llast:上上个数，int last:上个数,bool if3:三个连续的是否出现
于是你就有了一个六维dp辣~~:dp[pos][llast][last][if4][if8][if3].
具体看代码。
#include<iostream> #include<stdio.h> #include<cstring> #define LL long long using namespace std; LL dp[11][11][11][2][2][2]; int a[11];int cnt; inline LL calc(int pos,int llast,int last,bool if4,bool if8,bool if3,bool head,bool limit){ if(pos==-1) return if3?1:0;//如果出现过连续三个相同的数，才符合条件。 if(!limit && !head && last!=-1 && llast!=-1 && dp[pos][llast][last][if4][if8][if3]!=-1) return dp[pos][llast][last][if4][if8][if3]; int up=limit?a[pos]:9;//上限。 int down=head?1:0;//下限。 LL tmp=0; for(int i=down;i<=up;++i){ if(if4 && i==8) continue;//有4不能有8. if(if8 && i==4) continue;//有8不能有4. tmp+=calc(pos-1,last,i,if4||(i==4),if8||(i==8),if3||(llast==last&&last==i),0,limit && i==a[pos]); //传递条件就好啦。 } if(!limit && !head && last!=-1 && llast!=-1) dp[pos][llast][last][if4][if8][if3]=tmp; return tmp; } inline LL devide(LL x){ cnt=-1; memset(a,0,sizeof a); while(x){ a[++cnt]=x%10; x/=10; } return cnt!=10?0:calc(cnt,-1,-1,0,0,0,1,1);//不足11位返回零就好啦。 //不要说不存在这种情况。 //因为我们传的是l-1。所以l=100 0000 0000 时，l-1=99 9999 9999 辣。 } int main(){ LL l,r; cin>>l>>r; memset(dp,-1,sizeof dp); cout<<devide(r)-devide(l-1); return 0; }
就这样了吧。因为本人实在太弱，错了是很正常的，欢迎指正。不过希望能帮到你哦。