hdu3652（数位dp）

要求找出范围内含有“13”且能被13整除的数字的个数

可以使用数位dp

dp[i][j][0] 表示长度为i，余数为j，不含13的数字的个数

dp[i][j][1] 表示长度为i，余数为j，3开头的数字的个数

dp[i][j][2] 表示长度为i，余数为j，含有"13"的数字的个数

index[1] = 1;

for(i=2; i<11; ++i)

　　index[i] = (index[i-1] * 10) % 13;

index[i] 存储的为1,10,100,1000,10000 % 13 的余数

那么，状态转移方程详见源代码

 1 #include <stdio.h>
 2 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(i=2; i<11; ++i)
10         index[i] = (index[i-1]*10) % 13;
11     dp[0][0][0] = 1;
12     for(i=1; i<11; ++i)
13     {
14         for(k=0; k<13; ++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]*3+k)%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(j=0; j<10; ++j)
23             {
24                 //长度为i-1，余数为k的不含13的数字前面加上j-->长度为i，余数为(index[i]*j+k)%13不含13的数字个数
25                 //但是dp[i-1][k][0] 里面是包含dp[i-1][k][1]的，当加上数字1时，成为了含有13的数字，这里多加，所以在（1）处减去
26                 dp[i][(index[i]*j+k)%13][0] += dp[i-1][k][0];
27                 //长度为i-1，余数为k的含13的数字前面加上j-->长度为i，余数为(index[i]*j+k)%13含13的数字个数
28                 dp[i][(index[i]*j+k)%13][2] += dp[i-1][k][2];
29             }
30         }
31     }
32 }
33 int getAns(int n)
34 {
35     int i,j,k,len=0,ans=0;
36     while(n)
37     {
38         num[++len] = n % 10;
39         n /= 10;
40     }
41     num[len+1] = 0;
42     bool flag = false;
43     int t = 0,mod;
44     for(i=len; i>=1; --i)
45     {
46         for(k=0; k<13; ++k)
47         {
48             if(num[i]>1 && !flag)//第i位取1
49             {
50                 mod = (index[i]+k+t)%13;//第i位取1时余数为mod
51                 if(mod==0) ans += dp[i-1][k][1];//如果余数为0，那么就加上3开头的数字个数
52             }
53             if(num[i+1]==1 && num[i]>3 &&!flag)//第i+1位为1，第i位取3.
54             {
55                 mod = (t + k) % 13;//第i+1位为1，第i位取3的余数为mod
56                 if(mod==0) ans += dp[i][k][1];//如果余数为0，那么就加上3开头的数字个数
57             }
58             for(j=0; j<num[i]; ++j)//第i位为j时，
59             {
60                 mod = (index[i]*j+k+t)%13;//第i位为j时余数为mod
61                 if(mod==0) ans += dp[i-1][k][2];//如果余数为0，那么就加上含有13的数字的个数
62                 if(mod==0 && 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[i+1]==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
",getAns(n+1));
79     }
80     return 0;
81 }

View Code

数位dp的难点就在于状态的转移，还有统计。

关键要弄懂它统计的原理。

http://www.cnblogs.com/justPassBy/p/4275226.html