hdu 2089 不要62(数位dp入门)

http://acm.hdu.edu.cn/showproblem.php?pid=2089

数位dp(dfs)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int dp[34][3];
 8 int bit[34];
 9 
10 int dfs(int len,int is,int p)
11 {
12     if (!len) return 1;
13     if (!p&&dp[len][is]>=0) return dp[len][is];
14     int cut=0,mx=p ? bit[len] : 9;
15     for (int i=0;i<=mx;i++)
16     {
17         if (i==4||is&&i==2) continue;
18         cut+=dfs(len-1,i==6,p&&i==mx);
19     }
20     return p ? cut : dp[len][is]=cut;
21 }
22 
23 int f(int n)
24 {
25     int len=0;
26     while (n)
27     {
28         bit[++len]=n%10;
29         n/=10;
30     }
31     memset(dp,-1,sizeof(dp));
32     return dfs(len,0,1);
33 }
34 
35 int main()
36 {
37     int n,m;
38     while (~scanf("%d%d",&n,&m)&&n)
39     cout<<f(m)-f(n-1)<<endl;
40     return 0;
41 }

数位dp

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int dp[10][3];
 7 
 8 void Init()
 9 {
10     memset(dp,0,sizeof(dp));
11     dp[0][0]=1;
12     for (int i=1;i<=7;i++)
13     {
14         dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
15         dp[i][1]=dp[i-1][0];
16         dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];
17     }
18 }
19 
20 int f(int n)
21 {
22    int i=1,sum=0,s[10],flag=0,x=n;
23    while (n)
24    {
25        s[i++]=n%10;
26        n/=10;
27    }
28    s[i]=0;
29    for (;i;i--)
30    {
31        sum+=dp[i-1][2]*s[i];
32        if (flag) sum+=dp[i-1][0]*s[i];
33        else
34        {
35            if (s[i]>4) sum+=dp[i-1][0];
36            if (s[i]>6) sum+=dp[i-1][1];
37            if (s[i+1]==6&&s[i]>2) sum+=dp[i][1];
38        }
39        if (s[i]==4||(s[i]==2&&s[i+1]==6)) flag=1;
40    }
41    return x-sum;
42 }
43 
44 int main()
45 {
46     Init();
47     int n,m;
48     while (~scanf("%d%d",&n,&m)&n)
49     {
50         cout<<f(m+1)-f(n)<<endl;
51     }
52     return 0;
53 }

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int dp[10][3];
 7 
 8 void Init()
 9 {
10     memset(dp,0,sizeof(dp));
11     dp[0][0]=1;
12     for (int i=1;i<=7;i++)
13     {
14         dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
15         dp[i][1]=dp[i-1][0];
16         dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];
17     }
18 }
19 
20 int f(int n)
21 {
22    int i=1,sum=0,s[10],flag=0,x=n;
23    while (n)
24    {
25        s[i++]=n%10;
26        n/=10;
27    }
28    s[i]=0;
29    for (;i;i--)
30    {
31        sum+=dp[i-1][2]*s[i];
32        if (flag) sum+=dp[i-1][0]*s[i];
33        else
34        {
35            if (s[i]>4) sum+=dp[i-1][0];
36            if (s[i]>6) sum+=dp[i-1][1];
37            if (s[i+1]==6&&s[i]>2) sum+=dp[i][1];
38        }
39        if (s[i]==4||(s[i]==2&&s[i+1]==6)) flag=1;
40    }
41    return x-sum;
42 }
43 
44 int main()
45 {
46     Init();
47     int n,m;
48     while (~scanf("%d%d",&n,&m)&n)
49     {
50         cout<<f(m+1)-f(n)<<endl;
51     }
52     return 0;
53 }