首页 > 代码库 > BZOJ 4521 手机号码
BZOJ 4521 手机号码
SB数位dp.
我的貌似要特判9999999999的情况。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long l,r,dp[13][4][10][2][2][2],ret=0,bit[15]; void reset() { for (long long i=0;i<=11;i++) for (long long j=0;j<=3;j++) for (long long k=0;k<=9;k++) for (long long l=0;l<=1;l++) for (long long a=0;a<=1;a++) for (long long b=0;b<=1;b++) dp[i][j][k][l][a][b]=-1; } void get_bit(long long x) { ret=0; while (x) {bit[++ret]=x%10;x/=10;} } long long dfs(long long pos,long long cnt,long long num,long long f,long long f1,long long f2,bool flag) { if (!pos) return f; if ((!flag) && (dp[pos][cnt][num][f][f1][f2]!=-1)) return dp[pos][cnt][num][f][f1][f2]; long long ans=0,up=flag?bit[pos]:9,tc; for (long long i=0;i<=up;i++) { if ((i==4) && (f2)) continue; if ((i==8) && (f1)) continue; if (i==num) tc=min(cnt+1,3LL);else tc=1; ans+=dfs(pos-1,tc,i,f|(tc==3),f1|(i==4),f2|(i==8),flag&&(i==up)); } if (!flag) dp[pos][cnt][num][f][f1][f2]=ans; return ans; } long long ask(long long x) { get_bit(x); if (x==9999999999LL) return dfs(ret,1,0,0,0,0,1); else return dfs(ret,0,-1,0,0,0,1); } int main() { scanf("%lld%lld",&l,&r);reset(); printf("%lld\n",ask(r)-ask(l-1)); return 0; }
BZOJ 4521 手机号码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。