数目链接
题目大意：求[l,r]内出现至少3个相邻的相同数字，号码中不能同 时出现8和4的不含前导0的数字
题解：数位dp
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; #define INF 1e10 const int M=15; ll l,r; ll f[M][M][M][2][2]; int len,bit[M]; ll dfs(int x,int s,int k,bool et,bool fr,bool e){//位数，相同，上一位，8，4，终点 if(et&&fr) return 0; if(!x) return k==3; if(!e&&f[x][s][k][et][fr]!=-1) return f[x][s][k][et][fr]; ll res=0;int u=e?bit[x]:9; for(int i=x==len;i<=u;i++){//不枚举前导0，固定位数 if(!k) res+=dfs(x-1,i,1,et||i==8,fr||i==4,e&&i==u); else res+=dfs(x-1,i,(k==3?k:(i==s?k+1:1)),et||i==8,fr||i==4,e&&i==u); } return e?res:f[x][s][k][et][fr]=res; } ll solve(ll x){ len=0; while(x) bit[++len]=x%10,x/=10; return dfs(len,0,0,0,0,1); } void work(){ if(l==INF) cout<<solve(r); else cout<<solve(r)-solve(l-1); } void init(){ memset(f,-1,sizeof(f)); cin>>l>>r; } int main() { init(); work(); return 0; }