HDU 2089 - No 62 or 4

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

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

80

https://blog.csdn.net/wust_zzwh/article/details/52100392
入门题。就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。

typedef long long ll;
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int up=limit ? a[pos] : 9;
    int tmp=0;
    for(int i=0;i<=up;i++)
    {
        if(pre==6 && i==2)continue;
        if(i==4) continue;//都是保证枚举合法性
        tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=tmp;
    return tmp;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}
int main()
{
    int le,ri;
    //memset(dp,-1,sizeof dp);可优化
    while(~scanf("%d%d",&le,&ri) && le+ri)
    {
        memset(dp,-1,sizeof dp);
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}

http://www.calvinneo.com/2017/09/23/HDU2089%E4%B8%8D%E8%A6%8162/

这条题目是典型的求[L, R]区间内满足某性质的整数的数目问题，通常解法是用[0, R]区间的数目减去[0, L-1]区间的数目。数位DP是此类问题常见的解题思路。

数位dp其实类似于中记忆化搜索。数位DP由最深N$N$（N$N$为R$R$的十进制位数）层dfs组成。出于实现方便，数字123$123$映射到int nums[]数组中，首尾颠倒变成[3,2,1]$[3,2,1]$。由于从原数字的最高位往最末位递归，因此记忆化搜索的每次递归pos是从N−1$N-1$递减的。

1 2 3 4 5 6 7 8 9 10 11 12

LL solve(int x){ memset(nums, 0, sizeof nums); memset(dp, -1, sizeof dp); int ppos = 0; while (x != 0) { nums[ppos++] = x % 10; x /= 10; } // 开始dfs记忆化搜索 LL ans = dfs(ppos - 1, 0, true); return ans; }

flag表示在遍历当前pos位时，比pos位低的[0..pos−1]$[\mathrm{0..}pos-1]$位是否有限制，其初始值为true，因为最高位肯定是有限制的。例如数字234$234$，在遍历到cur[2]$cur[2]$为1$1$时，cur[2..1]$cur[\mathrm{2..1}]$能够取遍[10..19]$[\mathrm{10..19}]$，但是当cur[2]$cur[2]$为能取的上确界2$2$时，低位的cur[1]$cur[1]$只能够在[0..nums[1]]$[\mathrm{0..}nums[1]]$的范围里面取了，cur[2..1]$cur[\mathrm{2..1}]$取值为[21..23]$[\mathrm{21..23}]$。总结规律，只有前缀[pos+1..N−1]$[pos+1..N-1]$的flag为true（前缀的所有位都取到了上确界），且当前位pos的当前值cur[pos]$cur[pos]$也取上确界nums[pos]$nums[pos]$或9$9$时，低位cur[pos−1]$cur[pos-1]$只能取[0..nums[pos−1]]$[\mathrm{0..}nums[pos-1]]$，否则能自由取[0..9]$[\mathrm{0..9}]$。status用来表示状态，这个状态被用来计算当前子问题的结果，例如在这道题目中，status用来记录是否存在62或者4。

子结构一般为dp[pos][..]..$dp[pos][..]..$的多维数组。后面的几维与状态有关，有时候可能还需要进行离散化。从上面可知当flag为true的时候，不能取满[0..9]$[\mathrm{0..9}]$，此时我们就没必要记录下结果，因为显然取满的情况是占绝大多数的。因此dfs的结构如下

LL dfs(int pos, int status, bool flag) { if (pos == -1) { // 如果到达最深层，check是否继续满足题目中的性质 return check(status) ? 1 : 0; } if (!flag && dp[pos][status] != -1) { // 如果此层能够取满，那查看能不能复用存储的结果 return dp[pos][status]; } LL ans = 0; int end = flag ? nums[pos] : 9; // 如果flag为true就是不自由的，end只能取到nums[pos] for (int i = 0; i <= end; i++) { int newstatus = ...; // 如果最终结果与前缀的结果满足and或者or的性质，这里还可以剪枝 bool newflag = flag && (i == end); // 下一层的flag，注意要满足两个条件 ans += dfs(pos - 1, newstatus, newflag); } if (!flag) { // 只保存任何层取满[0..9]的结果 dp[pos][status] = ans; } return ans; }

https://111qqz.com/2016/03/hdu-2089/
https://gukaifeng.me/?p=368

¨对于一个小于n的数，肯定是从高位到低位出现某一位<n的那一位。

¨如 n = 58 n为十进制数。

¨  x = 49 此时x的十位<n

¨  x = 51 此时x的个位<n

¨有了上述性质，我们就可以从高到低枚举第一次<n对应位是哪一位。

这样之前的位确定了，之后的位就不受n的限制即从00…0~99…9，可以先预处理

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

int n,m;

int dp[30][2];

int digit[30];

int dfs (int pos,bool preis6,bool limit)  //pos表示从低到高的第几位，是从高位往低位递归的（也就是从左到又）

                                          // preis6 表示上一个数字是否为6，

                                          // limit表示该位置是否有限制。

{

//    cout<<pos<<" "<<preis6<<" "<<limit<<" "<<endl;

    if (pos==0) return 1; //到该位置表明找到了一个解.

    int res = 0 ;

    if (!limit&&dp[pos][preis6]!=-1) return dp[pos][preis6];  //如果不是limit位置，表示结果是通用的，而之前又算过的话，就可以直接调用这个结果。

    int mx = limit?digit[pos]:9; //mx第pos位置能取到的最大的数字..如果不是limit,则可以0..9任意取。

//    cout<<"mx:"<<mx<<endl;

    

    for ( int i = 0 ; i <= mx;  i++)

    {

        if (i==4||(i==2&&preis6)) continue;

        res += dfs(pos-1,i==6,limit&&i==mx);

        //(limit&&i==mx)中limit的含义是。。如果当前一位不是limit位（即0..9可以随便取的位置）

        //，那么之后的位置也一定不是limit位置。

        //而i==mx部分的意思是，在当前位置的数字小于当前位置的数字能取的最大值（mx）之前，

        //后面位的数字随便取也不会超过上界。

    }

    

    if (!limit) dp[pos][preis6]=res;  //记忆化. 非limit位的结果才通用，不然没必要存。

    return res;

}

int solve ( int n)

{

    ms(digit,0);  //将数按照每一位存到digit数组中

    int len = 0 ;

    while (n)

    {

        digit[++len] = n % 10;

        n/=10;

    }

    return dfs(len,false,true);

}

int main()

{

        #ifndef  ONLINE_JUDGE

        freopen("code/in.txt","r",stdin);

  #endif

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

        {

            if (n==0&&m==0) break;

            

            ms(dp,-1);

            int ans = solve (m)-solve(n-1);

            printf("%d\n",ans);

        }

  #ifndef ONLINE_JUDGE  

  fclose(stdin);

  #endif

    return 0;

}

https://yunhao.space/2018/06/17/acm-hdu-2089-digital-dp/

int n, m; int s[10]; int len; int dp[10][2]; int dfs(int pos, int lim, int prev){ if(pos < 0) return 1; if(lim == -1 && dp[pos][prev == 6] != 0) return dp[pos][prev == 6]; int up = lim==-1?9:lim; int tmp = 0; for(int i = 0; i <= up; i++){ if(i == 4) continue; if(i == 2 && prev == 6) continue; if(i == lim) tmp += dfs(pos-1, s[pos-1], i); else tmp += dfs(pos-1, -1, i); } if(lim == -1){ dp[pos][prev == 6] = tmp; } return tmp; } int solve(int num){ len = 0; memset(s, 0, sizeof s); while(num > 0){ s[len++] = num % 10; num /= 10; } return dfs(len-1, s[len-1], -1); } int main(){ while(~scanf("%d %d", &n, &m)){ if(n == 0 && m == 0) break; memset(dp, 0, sizeof dp); printf("%d\n", solve(m)-solve(n-1)); } return 0; }

https://blog.csdn.net/wust_zzwh/article/details/52100392
就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。

dp[len][0 / 1] 表示不含 4 和 62的前提下，剩余长度为 len ，首位是否为 6 的个数。

思路大概是依次把每位作为最高位，枚举这位可取的数字，决定后面需要的状态，相加，都不需要照着转移方程写了。

X.
https://www.cnblogs.com/alihenaixiao/p/4917631.html

　　用数位dp做这个题目的时候，首先要预处理出dp[x][y]，代表以y开头的x位数中不含有62和4的数有多少个，在满足条件的情况下状态转移为：dp[x][y] += dp[x-1][k]。又因为对于一个数字x，如果和它位数相同的数字y小于x，那么只需要y数字其中任意一位小于x即可。然后问题就变为求ans([1, r+1]) - ans([1, l])。

12 void init ()
13 {
14     memset(dp, 0, sizeof(dp));
15     dp[0][0] = 1;
16     for (int i=1; i<=7; i++)//i位数
17         for (int j=0; j<10; j++)//第i位数
18             for (int k=0; k<10; k++)//第i-1位数
19             {
20                 if(j==4 || j==6&&k==2)
21                     continue ;
22                 dp[i][j] += dp[i-1][k];
23             }
24 }
25 
26 int solve (int n)
27 {
28     int a[maxn], len = 0, ans = 0;
29     while (n)
30     {
31         a[++len] = n % 10;
32         n /= 10;
33     }
34     a[len+1] = 0;
35 
36     for (int i=len; i>0; i--)
37     {//枚举后len位的策略
38         for (int j=0; j<a[i]; j++)
39         {
40             if (j==4 || a[i+1]==6&&j==2)
41                 continue ;
42             ans += dp[i][j];
43         }
44 
45         if (a[i]==4 || a[i+1]==6 && a[i]==2)
46             break;
47     }
48     return ans;
49 }
50 
51 int main ()
52 {
53     int n, m;
54     init ();
55 
56     while (scanf ("%d %d", &n, &m), n + m)
57         printf ("%d\n", solve(m+1) - solve(n));
58     return 0;
59 }