hdu 3709+hdu 3555(数位dp)

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

数位dp...完全看大牛模版理解的。。。。

View Code

 1 #include<iostream>
 2 using namespace std;
 3 __int64 dp[19][19][2000];
 4 int digit[19];
 5 
 6 //pos表示当前的位置,o表示支点，pre表示从最高位到pos的力矩之和，doing表示是否有上限，若无，则为9;
 7 __int64 dfs(int pos,int o,int pre,bool doing){
 8     if(pos==-1){
 9         return pre==0;  //已经全部组合
10     }
11     if(pre<0)return 0;//如果前面组合的力矩之和已经为负，则后面的必然小于0；
12     //没有上限，且前面的状态已经搜过
13     if(!doing&&dp[pos][o][pre]!=-1){
14         return dp[pos][o][pre];
15     }
16     __int64 ans=0;
17     int end=doing?digit[pos]:9;
18     for(int i=0;i<=end;i++){
19         int npre=pre;   //枚举下一个状态
20         npre+=(pos-o)*i;   
21         ans+=dfs(pos-1,o,npre,doing&&i==end);
22     }
23     if(!doing){
24         dp[pos][o][pre]=ans;
25     }
26     return ans;
27 }
28 
29 __int64 solve(__int64 n){
30     int pos=0;
31     while(n){
32         digit[pos++]=n%10;
33         n/=10;
34     }
35     __int64 ans=0;
36     for(int o=0;o<pos;o++){
37         ans+=dfs(pos-1,o,0,1);
38     }
39     return ans-(pos-1);//0,00,000....这种情况
40 }
41 
42 int main(){
43     int _case;
44     scanf("%d",&_case);
45     memset(dp,-1,sizeof(dp));
46     while(_case--){
47         __int64 n,m;
48         scanf("%I64d%I64d",&n,&m);
49         printf("%I64d\n",solve(m)-solve(n-1));
50     }
51     return 0;
52 }

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

View Code

 1 #include<iostream>
 2 using namespace std;
 3 __int64 dp[20][3];
 4 int digit[20];
 5 
 6 //have==1表示前一位为4,have==0表示没有出现49，have==2表示前面有49出现
 7 __int64 dfs(int pos,int have,bool doing){
 8     if(pos==-1){
 9         return have==2;//找到一个解
10     }
11     if(!doing&&dp[pos][have]!=-1){
12         return dp[pos][have];
13     }
14     __int64 ans=0;
15     int end=doing?digit[pos]:9;
16     for(int i=0;i<=end;i++){
17         int nhave=have;
18         if(have==1&&i!=4){
19             nhave=0;
20         }
21         if(have==0&&i==4){
22             nhave=1;
23         }
24         if(have==1&&i==9){
25             nhave=2;
26         }
27         ans+=dfs(pos-1,nhave,doing&&i==end);
28     }
29     if(!doing)
30         dp[pos][have]=ans;
31     return ans;
32 }
33 
34 __int64 solve(__int64 n){
35     int pos=0;
36     while(n){
37         digit[pos++]=n%10;
38         n/=10;
39     }
40     return dfs(pos-1,0,1);
41 }
42 
43 int main(){
44     int _case;
45     scanf("%d",&_case);
46     memset(dp,-1,sizeof(dp));
47     while(_case--){
48         __int64 n;
49         scanf("%I64d",&n);
50         printf("%I64d\n",solve(n));
51     }
52     return 0;
53 }

昨天做的fzu的月赛。。。当时没过。。。

http://acm.fzu.edu.cn/contest/problem.php?cid=126&sortid=1

这个代码我没提交过。。。

View Code

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

PS:记忆化搜索真的很强大啊。。。