首页 > 代码库 > bzoj 4521: [Cqoi2016]手机号码
bzoj 4521: [Cqoi2016]手机号码
感觉get到了一种数位dp的新姿势,加一位表示当前要填的数有没有限制(感觉以前的写法都太蠢了).
这么写有两个地方要注意：
1.每dp到一位时需要f[i][初始状态]++，相当于这位前都是前导零(这道题我把前两位填了两个10作为初始状态)。
2.因为有了1，所以初始状态后的第一位不能填0，需要特判
f[i][j][k][l][p][q][o]表示填到第几位，上上位和上位分别是什么，4,8是否出现过，三个连续的是否出现过，以及当前位是否有限制。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;ll pw[100];ll f[20][11][11][2][2][2][2];// 位数 上位 这位 4 8 出现0/1 限制0/1 ll solve(ll x){ pw[0]=1; for(int i=1;i<=12;i++)pw[i]=pw[i-1]*10; int pos; for(int i=0;i<=12;i++)if(x>=pw[i])pos=i+1; memset(f,0,sizeof(f)); f[0][10][10][0][0][0][1]=1; for(int i=1;i<=pos;i++) { int ks=x/pw[pos-i]%10; f[i][10][10][0][0][0][0]=1; // 刷表 for(int j=0;j<=10;j++) { for(int k=0;k<=10;k++) { for(int l=0;l<=1;l++) { for(int p=0;p<=1;p++) { // 这位 for(int q=0;q<=9;q++) { if(j==10&&k==10&q==0)continue; bool b1=0,c1=0,d1=0; if(j==k&&j==q)b1=1; if(q==4)c1=1; if(q==8)d1=1; f[i][k][q][l|c1][p|d1][1][0]+=f[i-1][j][k][l][p][1][0]; f[i][k][q][l|c1][p|d1][b1][0]+=f[i-1][j][k][l][p][0][0]; } for(int q=0;q<=ks;q++) { if(j==10&&k==10&q==0)continue; bool b1=0,c1=0,d1=0; if(j==k&&j==q)b1=1; if(q==4)c1=1; if(q==8)d1=1; if(q!=ks) { f[i][k][q][l|c1][p|d1][1][0]+=f[i-1][j][k][l][p][1][1]; f[i][k][q][l|c1][p|d1][b1][0]+=f[i-1][j][k][l][p][0][1]; } else { f[i][k][q][l|c1][p|d1][1][1]+=f[i-1][j][k][l][p][1][1]; f[i][k][q][l|c1][p|d1][b1][1]+=f[i-1][j][k][l][p][0][1]; } } } } } } } ll ans=0; for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)for(int k=0;k<=1;k++)for(int l=0;l<=1;l++)for(int s=0;s<=1;s++) { if(k&&l)continue; ans+=f[pos][i][j][k][l][1][s]; } return ans;}ll l,r;int main(){ scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); return 0;}
bzoj 4521: [Cqoi2016]手机号码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。