网站内容协议,上海公司招聘信息,如何检测网站的打开速度,邵阳做网站价格要求找出范围内含有“13”且能被13整除的数字的个数 可以使用数位dp dp[i][j][0] 表示长度为i#xff0c;余数为j#xff0c;不含13的数字的个数 dp[i][j][1] 表示长度为i#xff0c;余数为j#xff0c;3开头的数字的个数 dp[i][j][2] 表示长度为i#xff0c;余数为j…要求找出范围内含有“13”且能被13整除的数字的个数 可以使用数位dp dp[i][j][0] 表示长度为i余数为j不含13的数字的个数 dp[i][j][1] 表示长度为i余数为j3开头的数字的个数 dp[i][j][2] 表示长度为i余数为j含有13的数字的个数 index[1] 1; for(i2; i11; i) index[i] (index[i-1] * 10) % 13; index[i] 存储的为1,10,100,1000,10000 % 13 的余数 那么状态转移方程详见源代码 1 #include stdio.h2 int dp[11][13][3];3 int index[11];4 int num[11];5 void init()6 {7 int i,j,k;8 index[1] 1;9 for(i2; i11; i)
10 index[i] (index[i-1]*10) % 13;
11 dp[0][0][0] 1;
12 for(i1; i11; i)
13 {
14 for(k0; k13; k)
15 {
16 //1
17 dp[i][(index[i]k)%13][0] - dp[i-1][k][1];
18 //长度为i-1,余数为k的不含13的数字前面加上3,--长度为i-1余数为k的3开头的个数
19 dp[i][(index[i]*3k)%13][1] dp[i-1][k][0];
20 //长度为i-1余数为k的3开头的数字前面加上1--长度为i余数为(index[i]k)%13含13的数字个数
21 dp[i][(index[i]k)%13][2] dp[i-1][k][1];
22 for(j0; j10; j)
23 {
24 //长度为i-1余数为k的不含13的数字前面加上j--长度为i余数为(index[i]*jk)%13不含13的数字个数
25 //但是dp[i-1][k][0] 里面是包含dp[i-1][k][1]的当加上数字1时成为了含有13的数字这里多加所以在1处减去
26 dp[i][(index[i]*jk)%13][0] dp[i-1][k][0];
27 //长度为i-1余数为k的含13的数字前面加上j--长度为i余数为(index[i]*jk)%13含13的数字个数
28 dp[i][(index[i]*jk)%13][2] dp[i-1][k][2];
29 }
30 }
31 }
32 }
33 int getAns(int n)
34 {
35 int i,j,k,len0,ans0;
36 while(n)
37 {
38 num[len] n % 10;
39 n / 10;
40 }
41 num[len1] 0;
42 bool flag false;
43 int t 0,mod;
44 for(ilen; i1; --i)
45 {
46 for(k0; k13; k)
47 {
48 if(num[i]1 !flag)//第i位取1
49 {
50 mod (index[i]kt)%13;//第i位取1时余数为mod
51 if(mod0) ans dp[i-1][k][1];//如果余数为0那么就加上3开头的数字个数
52 }
53 if(num[i1]1 num[i]3 !flag)//第i1位为1第i位取3.
54 {
55 mod (t k) % 13;//第i1位为1第i位取3的余数为mod
56 if(mod0) ans dp[i][k][1];//如果余数为0那么就加上3开头的数字个数
57 }
58 for(j0; jnum[i]; j)//第i位为j时
59 {
60 mod (index[i]*jkt)%13;//第i位为j时余数为mod
61 if(mod0) ans dp[i-1][k][2];//如果余数为0那么就加上含有13的数字的个数
62 if(mod0 flag) ans dp[i-1][k][0];//如果余数为0且前面的数字含有13那么就加上不含13的数字个数
63 }
64 }
65 t (t num[i]*index[i])%13;//第len位到第i位的数字固定后产生的余数
66 if(num[i1]1 num[i]3)
67 flag true;
68 }
69 return ans;
70 }
71 int main()
72 {
73 int n;
74 init();
75
76 while(scanf(%d,n)!EOF)
77 {
78 printf(%d\n,getAns(n1));
79 }
80 return 0;
81 } View Code 数位dp的难点就在于状态的转移还有统计。 关键要弄懂它统计的原理。 http://www.cnblogs.com/justPassBy/p/4275226.html转载于:https://www.cnblogs.com/justPassBy/p/4277263.html
