数位dp

题目链接：http://acdreamoj.sinaapp.com/problem.php?id=1083

没什么好说的，具体看代码吧。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int dp[11][4];//0没有3和8，1只有3，2只有8，3有3和8
 7 int digit[11];
 8 
 9 int dfs(int pos,int have,int doing){
10     if(pos==-1){
11         return have==1||have==2;
12     }
13     if(!doing&&dp[pos][have]!=-1){
14         return dp[pos][have];
15     }
16     int ans=0;
17     int end=doing?digit[pos]:9;
18     for(int i=0;i<=end;i++){
19         int nhave=have;
20         if(i==3&&(have==0||have==1))nhave=1;
21         else if(i==3&&(have==2||have==3))nhave=3;
22         else if(i==8&&have==0)nhave=2;
23         else if(i==8&&(have==1||have==3))nhave=3;
24         ans+=dfs(pos-1,nhave,doing&&i==end);
25     }
26     if(!doing)
27         dp[pos][have]=ans;
28     return ans;
29 }
30 
31 
32 int Solve(int n){
33     int pos=0;
34     while(n){
35         digit[pos++]=n%10;
36         n/=10;
37     }
38     return dfs(pos-1,0,1);
39 }
40 
41 
42 int main(){
43     memset(dp,-1,sizeof(dp));
44     int _case,n,m;
45     scanf("%d",&_case);
46     while(_case--){
47         scanf("%d%d",&n,&m);
48         printf("%d\n",Solve(m)-Solve(n-1));
49     }
50     return 0;
51 }

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4389

思路：dp[i][j][k][l]表示位数i,各位数总和为j,k=mod(l)的数的个数，而1<=l<=81，故我们可以枚举l的值来进行记忆化搜索。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int dp[11][88][88][88];
 7 //dp[i][j][k][l].i表示位数,j表示前面数字的和,k表示mod l的值,l表示和
 8 int digit[11];
 9 int res;
10 
11 int dfs(int pos,int sum,int mod,int doing){
12     if(pos==-1){
13         return mod==0&&sum==res;
14     }
15     if(res<sum)return 0;
16     if(!doing&&dp[pos][sum][mod][res]!=-1){
17         return dp[pos][sum][mod][res];
18     }
19     int ans=0;
20     int end=doing?digit[pos]:9;
21     for(int i=0;i<=end;i++){
22         int nsum=sum+i;
23         int nmod=(mod*10+i)%res;
24         ans+=dfs(pos-1,nsum,nmod,doing&&i==end);
25     }
26     if(!doing)
27         dp[pos][sum][mod][res]=ans;
28     return ans;
29 }
30 
31 
32 
33 int Solve(int n){
34     int pos=0,ans=0;
35     while(n){
36         digit[pos++]=n%10;
37         n/=10;
38     }
39     for(res=1;res<=82;res++){
40         ans+=dfs(pos-1,0,0,1);
41     }
42     return ans;
43 }
44 
45 int main(){
46     memset(dp,-1,sizeof(dp));
47     int _case,t=1,n,m;
48     scanf("%d",&_case);
49     while(_case--){
50         scanf("%d%d",&n,&m);
51         printf("Case %d: %d\n",t++,Solve(m)-Solve(n-1));
52     }
53     return 0;
54 }
55 
56

View Code