首页 > 代码库 > HDU 4734 F(x)
HDU 4734 F(x)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意：对于一个n位的十进制数字x=(AnAn-1An-2 ... A2A1)，定义 F(x)=An*2n-1+An-1*2n-2+ ...+A2*2+A1*1。给出A、B，求在[0,B]之间有多少数字满足F(x)<=F(A)？
思路：数位DP。f[dep][x]表示到达dep剩余为x的方案数。
i64 n,m;i64 f[25][N];int a[25],num;i64 Sum;i64 DFS(int dep,int flag,int cur){ if(cur<0) return 0; if(dep==-1) return 1; if(!flag&&f[dep][cur]!=-1) return f[dep][cur]; int M=flag?a[dep]:9; i64 ans=0,i; for(i=0;i<=M;i++) { ans+=DFS(dep-1,flag&&i==M,cur-i*(1<<dep)); } if(!flag) f[dep][cur]=ans; return ans;}i64 cal(){ num=0; while(n) a[num++]=n%10,n/=10; Sum=0; int i,j; FOR0(i,num) Sum+=a[i]*(1<<i); num=0; while(m) a[num++]=m%10,m/=10; return DFS(num-1,1,Sum);}int main(){ clr(f,-1); int num=0; rush() { scanf("%I64d%I64d",&n,&m); printf("Case #%d: %I64d\n",++num,cal()); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。