HDU 4722 Good Numbers(DP)

脑子有点乱，有的地方写错了，尚大婶鄙视了。。。

来个模版的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LL __int64
 6 LL dp[31][31];
 7 int num[31];
 8 LL dfs(int pos,int pre,int bound)
 9 {
10     int end,tpre,i;
11     LL ans = 0;
12     if(pos == -1)
13     return pre == 0;
14     if(!bound&&dp[pos][pre] != -1)
15     return dp[pos][pre];
16     end = bound ? num[pos] : 9;
17     for(i = 0;i <= end;i ++)
18     {
19         tpre = (pre + i)%10;
20         ans += dfs(pos-1,tpre,bound&&i == end);
21     }
22     if(!bound)
23     dp[pos][pre] = ans;
24     return ans;
25 }
26 LL judge(LL x)
27 {
28     int pos = 0;
29     if(x < 0)
30     return 0;
31     while(x)
32     {
33         num[pos++] = x%10;
34         x = x/10;
35     }
36     return dfs(pos-1,0,1);
37 }
38 int main()
39 {
40     int t,cas = 1;
41     LL x,y;
42     memset(dp,-1,sizeof(dp));
43     scanf("%d",&t);
44     while(t--)
45     {
46         scanf("%I64d%I64d",&x,&y);
47         printf("Case #%d: ",cas++);
48         printf("%I64d
",judge(y)-judge(x-1));
49     }
50     return 0;
51 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <map>
 6 #include <ctime>
 7 #include <cmath>
 8 #include <algorithm>
 9 using namespace std;
10 #define LL __int64
11 LL dp[31][11];
12 LL judge(LL x)
13 {
14     int num[21],n = 0,sum,i,j;
15     LL ans = 0;
16     if(x < 0)
17     return 0;
18     else if(x == 0)
19     return 1;
20     while(x)
21     {
22         num[n ++] = x%10;
23         x /= 10;
24     }
25     if(n == 1)
26     return 1;
27     ans = dp[n-1][0];
28     for(i = 1;i < num[n-1];i ++)
29     {
30         ans += dp[n-1][10-i];
31     }
32     sum = num[n-1];
33     for(i = n-2;i >= 0;i --)
34     {
35         if(i == 0)
36         {
37             for(j = 0;j <= num[i];j ++)
38             if((sum + j)%10 == 0)
39             ans ++;
40             break;
41         }
42         for(j = 0;j < num[i];j ++)
43         ans += dp[i][(20-sum-j)%10];
44         sum = (sum + num[i])%10;
45     }
46     return ans;
47 }
48 int main()
49 {
50     int i,j,k,t,cas = 1;
51     LL x,y;
52     for(i = 0;i < 10;i ++)
53     dp[1][i] = 1;
54     for(i = 2;i <= 20;i ++)
55     {
56         for(j = 0;j < 10;j ++)
57         {
58             for(k = 0;k < 10;k ++)
59             {
60                 dp[i][(j+k)%10] += dp[i-1][j];
61             }
62         }
63     }
64     scanf("%d",&t);
65     while(t--)
66     {
67         scanf("%I64d%I64d",&x,&y);
68         printf("Case #%d: %I64d
",cas ++,judge(y)-judge(x-1));
69     }
70     return 0;
71 }