hdu 4722 Good numbers（数位DP）

hdu 4722 Good numbers（数位DP）

题目： ​​ i=1;i<=cnt;i++){ for(int j=0;j<10;j++){ for(int k=0;k<10;k++){ dp[i][(j+k)%10]+=dp[i-1][j]; } } for(int j=0;j

自己写一遍理解了些许，bit[20]存储十进制位数，dp[i][j]代表长度是i的数字所有位上数字之和%10得到的余数j的个数，简单例子：

对于23，比第一位数字小的有j=0,j=1，先计算上，dp[1][j]++（x=0)，然后将2记录下来，第一位处理完毕

比第二位数字小的有j=0,j=1,j=2，dp[2][j+x]++。长度更长的数字下一位原则上是什么数字(0--9)都存在可能，所以所有的dp[i][余数]都加上前者的个数

一个中间过程： 4

0 23

b=23

1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0

2 2 3 3 3 2 2 2 2 2

a-1=-1

out:2

#include #include #include using namespace std;typedef long long LL;LL bit[20],dp[20][10]; //dp: 长度i的数字数位求和余数是j的数字个数int cnt;LL work(LL n){ if(n<0) return 0; LL temp=n; cnt=0; memset(dp,0,sizeof(dp)); while(temp){ bit[++cnt]=temp%10; temp/=10; } for(int i=1;i<=cnt/2;/*cnt-i+1>=i;*/ i++){ //交换 高低位互换 bit[i]=bit[i]^bit[cnt-i+1]; bit[cnt-i+1]=bit[i]^bit[cnt-i+1]; bit[i]=bit[i]^bit[cnt-i+1]; } int x=0; for(int i=1;i<=cnt;i++){ for(int j=0;j<10;j++){ for(int k=0;k<10;k++){ //向后堆积 下一低位0——9均有可能 dp[i][(j+k)%10]+=dp[i-1][j]; } } for(int j=0;j>t; while(t--){ scanf("%I64d%I64d",&a,&b); printf("Case #%d: %I64d\n",++ca,work(b)-work(a-1)); } return 0;}

还发现一个问题，如果用异或交换两个数，那么那个bit[]代码里for的限制条件应该是i<=cnt/2，因为cnt-i+1>=i会使得数字自己交换自己，而l类似于：

int a=10; a=a^a; a=a^a; a=a^a;

的交换输出的是0。当然，如果是：

for(int i=1;cnt-i+1>=i;i++){ //交换 高低位互换 int t=bit[i]; bit[i]=bit[cnt-i+1]; bit[cnt-i+1]=t; }

也是可以的。

哎，还有很多的东西要学习。。。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。