HDu 4722(記憶化検索)
8372 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4722
考え方:簡単な記憶検索で、A=0の場合に注意すればいい.
View Code
考え方:簡単な記憶検索で、A=0の場合に注意すればいい.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 typedef long long ll;
7
8 int digit[22];
9 ll dp[22][12];
10
11 ll dfs(int pos,int pre,int doing)
12 {
13 if(pos==-1){
14 return pre==0;
15 }
16 if(!doing&&dp[pos][pre]!=-1){
17 return dp[pos][pre];
18 }
19 int end=doing?digit[pos]:9;
20 ll ans=0;
21 for(int i=0;i<=end;i++){
22 int npre=(pre+i)%10;
23 ans+=dfs(pos-1,npre,doing&&i==end);
24 }
25 if(!doing){
26 dp[pos][pre]=ans;
27 }
28 return ans;
29 }
30
31
32 ll Solve(ll n)
33 {
34 int pos=0;
35 while(n){
36 digit[pos++]=n%10;
37 n/=10;
38 }
39 return dfs(pos-1,0,1);
40 }
41
42 int main()
43 {
44 ll a,b;
45 int t=1,_case;
46 memset(dp,-1,sizeof(dp));
47 scanf("%d",&_case);
48 while(_case--){
49 scanf("%I64d%I64d",&a,&b);
50 printf("Case #%d: ",t++);
51 if(a==0){
52 printf("%I64d
",Solve(b));
53 }else
54 printf("%I64d
",Solve(b)-Solve(a-1));
55 }
56 return 0;
57 }
58
59
60 View Code