P4124——手机号码

为什么我感觉数位dp都长得一样呢，好像直接记搜都能过？？？ 第一个脑回路清晰的数位dp。记一下上一个，上上个，有没有限制，有没有4，有没有8，然后直接dfs爆搜就完了。 不过这有坑，就是一开始初始化的时候第len-1的上上个，不能赋成一个贼大的值，比9大即可。还有一个就是要判边界，当l==10000000000时，直接输出slove(r); ```cpp #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<map> #include<set> #define ri register int #define max maxx #define min minn using namespace std; template <class T> void in(T &x) { x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); } if (f) x = -x; } inline int maxx(int x,int y) { return x>y?x:y; } inline int minn(int x,int y) { return x<y?x:y; } inline int gcd(int x,int y) { return !y?x:gcd(y,x%y); } long long dp[20][11][11][4][4][4],l,r,len,ans,flag,num[20]; inline long long dfs(int temp,int last,int lasts,int limit,int ans,int four,int eight) { if(temp<=0) return ans; if((!limit)&&dp[temp][last][lasts][ans][four][eight]) return dp[temp][last][lasts][ans][four][eight]; long long lim=limit?num[temp]:9,tmp=0; for(ri i=0; i<=lim; ++i) { if((i==last)&&(last==lasts)) flag=1; else flag=0; if(i==4&&eight) continue; if(i==8&&four) continue; tmp+=dfs(temp-1,i,last,limit&&i==lim,ans||flag,four||i==4,eight||i==8); } return !limit?dp[temp][last][lasts][ans][four][eight]=tmp:tmp; } inline long long solve(long long x) { ans=0; len=0; memset(dp,0,sizeof dp); while(x) num[++len]=(x%10),x/=10; for(ri i=1; i<=num[len]; ++i) ans+=dfs(len-1,i,233,(i==num[len]),0,i==4,i==8); return ans; } int main() { scanf("%lld%lld",&l,&r); l==10000000000?printf("%lld",solve(r)):printf("%lld",solve(r)-solve(l-1)); return 0; } ```