首页 > 代码库 > xbz分组题B 吉利数字 数位dp入门
xbz分组题B 吉利数字 数位dp入门
B吉利数字
时限：1s
【题目描述】
算卦大湿biboyouyun最近得出一个神奇的结论，如果一个数字，它的各个数位相加能够被10整除，则称它为吉利数。现在叫你计算某个区间内有多少个吉利数字。
【输入】
第一行为样例个数N。接下来N行，每一行代表一个输入样例，每个输入样例有2个数，分别代表某个区间的起点a和终点b。
注意所求区间为[a,b]，1<=a<=b<=10^9
【输出】
N行。对于第x个输入样例，在第x行输入该样例所对应的结果。
【输入样例】
2
1 10
1 20
【输出样例】
0
1
【Hint】1-10之内无幸运数，1-20内只有19 这1个幸运数
------------------------------------------------------------------------------------
数位dp入门题。
一开始参考了数位dp入门ppt的非递归写法，先打个表再计算，结果YY了半天还是错了T^T
这里有个用dfs写法写数位dp的模板：
http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html
代码：
1 #include <stdio.h> 2 #include <string.h> 3 int dp[100][100]; 4 int dig[100]; 5 6 int dfs(int i,int s,bool e) 7 { 8 if (!i) return (s==0?1:0); 9 if ((!e)&&(dp[i][s]!=-1)) return dp[i][s];10 int res=0;11 int u=e?dig[i]:9;12 for (int q=0;q<=u;q++)13 res+=dfs(i-1,(s+q)%10,e&&q==u);14 if (!e) dp[i][s]=res;15 return res;16 }17 18 int f(int n)19 {20 int len = 0;21 while(n)22 {23 dig[++len] = n % 10;24 n /= 10;25 }26 return dfs(len,0,true);27 }28 29 int main()30 {31 int a,b,T;32 memset(dp,-1,sizeof(dp));33 scanf("%d",&T);34 while (T--)35 {36 scanf("%d %d",&a,&b);37 printf("%d\n",f(b)-f(a-1));38 }39 return 0;40 }
核心部分：（来自neopenx大神，orz）
1 int dfs(int len,int remain,bool fp) 2 { 3 if(!len) return remain==0?1:0; 4 if(!fp&&dp[len][remain]!=-1) 5 return dp[len][remain]; 6 int ret=0,fpmax=fp?digit[len]:9; 7 for(int i=0;i<=fpmax;i++) 8 ret+=dfs(len-1,(remain+i)%10,fp&&i==fpmax); 9 if(!fp) dp[len][remain]=ret;10 return ret;11 }12 13 int f(int n)14 {15 int len=0;16 while(n)17 {18 digit[++len]=n%10;19 n/=10;20 }21 return dfs(len,0,true);22 }
len：表示当前扫描到的数的位数，从高位向地位扫描
remain：表示当前状态。如本题中表示从最高位到当前位各位数字和%10
fp：又叫first place，neopenx的大神的理解是第一次打表
该dfs函数的基本思想也是打个表记下来，边记边用
fpmax:当前最高位
扩展：hdu2089
http://blog.csdn.net/dgq8211/article/details/9296953
xbz分组题B 吉利数字 数位dp入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。