【HDOJ 2089】不要62

第一个数位dp的题 做的老困难了。。。只是好歹是做出来了 迈出了第一步。。

对大牛来说这样的题都是小case

ps:新上一个记忆化方法 一些绕弯的题里用dfs好想些

代码例如以下:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int dp[8][3];

/*

dp[i][0]无不吉利数字

dp[i][1]无不吉利数字且高位为2

dp[i][2】有不吉利数字

*/

void Init()

{

    memset(dp,0,sizeof(dp));

    dp[0][0] = 1;

    int i;

    for(i = 1; i <= 8; ++i)

    {

        dp[i][0]=dp[i-1][0]*9-dp[i-1][1];  //在最高位加上除了4之外的9个数字，可是可能在2之前加了6

        dp[i][1]=dp[i-1][0];    //在原先不含不吉利数字的最高位加2

        dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];  //在已经有不吉利数字最高位加随意数字。或者在无吉利数字前加4，或者在2前面加4

    }

}

int Solve(int n)

{

    int ls[9],len = 0,i,ans,tmp = n,flag = false;

    while(n)

    {

        ls[++len] = n%10;

        n /= 10;

    }

    ans = ls[len+1] = 0;

    for(i = len; i; --i)

    {

        ans += dp[i-1][2]*ls[i];

        if(flag) //高位已出现4或62 后面随意加

            ans += dp[i-1][0]*ls[i];

        if(!flag && ls[i] > 4) //高位有出现4的可能

            ans += dp[i-1][0];

        if(!flag && ls[i+1] == 6 && ls[i] > 2)//高位有出现62的可能

            ans += dp[i][1];

        if(!flag && ls[i] > 6)

            ans += dp[i-1][1];

        if(ls[i] == 4 || (ls[i+1] == 6 && ls[i] == 2)) //出现4或62

            flag = 1;

    }

    return tmp - ans;

}

int main()

{

    int n,m;

    Init();

    while(~scanf("%d %d",&n,&m) && n && m)

    {

        printf("%d\n",Solve(m)-Solve(n-1));//[m,n]区间

    }

    return 0;

}

//记忆化

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int dp[8][3],digit[8];

/*

hav =

2 不含不吉利数字

1 不含不吉利数字 最高位6

0 含不吉利数字

high:前面是否出现高位(即当前位置可不能够随便填

*/

int dfs(int pos,int hav,bool high)

{

    if(pos == -1) return hav == 0;

    if(!high && ~dp[pos][hav]) return dp[pos][hav];

    int en = high? digit[pos]: 9;

    int i,ans = 0,nhav;

    for(i = 0; i <= en; ++i)

    {

        nhav = hav;

        if((hav == 1 && i == 2) || i == 4) nhav = 0;

        else if(hav == 2 && i == 6) nhav = 1;

        else if(hav == 1 && i != 6) nhav = 2;

        ans += dfs(pos-1,nhav,high && i == en);

    }

    if(!high) dp[pos][hav] = ans;

    return ans;

}

int Solve(int x)

{

    memset(dp,-1,sizeof(dp));

    int len = 0,tmp = x;

    while(x)

    {

        digit[len++] = x%10;

        x /= 10;

    }

    return tmp - dfs(len-1,2,1);

}

int main()

{

    int n,m;

    while(~scanf("%d %d",&n,&m) && n)

    {

        printf("%d\n",Solve(m) - Solve(n-1));

    }

    return 0;

}