数位DP

所谓数位DP，就是把一个数按照k进制数的每一个位展开，在把每一位的信息作为状态来推出答案。

比如：12345这个数在十进制下可拆为1、2、3、4、5，个位可以推十位，十位可以推百位，以此类推。
推状态的方法有很多，一般来说第一反应就是像普通dp一样从前往后推，但是由于思维难度较高而且写起来难度较大，所以推荐递归写法，也就是记忆话搜索的写法。

以HDU2089 不要62为例。

统计l,r区间内不含62,4的数字个数。

l~r区间符合条件的数字没有普遍的规律，状态数目过多不好做DP。但是1~x一段连续的区间在枚举数字时有大量重复状出现，利用记忆化搜索做DP。

一、首先将问题拆分成两部分，也就是1~r区间内符合条件数字的数目减去1~(l-1)区间内符合条件数字的数目。

ans=solve(r)-solve(l-1);

二、将输入的边界x转化为k进制存入数组备用。

int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}

三、安位枚举所有的数字，过程中发现状态已经搜索过，就可以直接返回答案（记忆化）

int dfs(int pos,int pre,int sta,bool limit)//pos当前数位,pre上一个数字,sta：pre是否为6，limit代表是否有至少有一个高位小于数位限制，如果小于的话，后面所有数位均无限制条件。
{
    if(pos==-1)return 1;                            //搜索到最后一位时，就说明找到了一个符合条件数
    if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];//非limit表示后面的数位无特殊限制，这里产生了大量重复子问题，而limit条件下后面每一位都认为是特殊的，不会被重复枚举，记忆化无用。     
    int up=limit?a[pos]:9;                          //limit条件下对当前位增加特殊限制
    int temp=0;                                     //计数
    for(int i=0; i<=up; i++)
    {
        if(i==4)continue;
        if(pre==6&&i==2)continue;                  //跳过非法状态。
        temp+=dfs(pos-1,i,i==6,limit&&i==a[pos]);  //记忆化递归
    }
    if(!limit)dp[pos][sta]=temp;
    return temp;
}

整体代码

#include<bits/stdc++.h>
using namespace std;
int dp[20][2],a[20];
int n,m;
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 temp=0;
    for(int i=0; i<=up; i++)
    {
        if(i==4)continue;
        if(pre==6&&i==2)continue;
        temp+=dfs(pos-1,i,i==6,limit&&i==a[pos]);
    }
    if(!limit)dp[pos][sta]=temp;
    return temp;
}
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 l,r;

    while(~scanf("%d%d",&l,&r)&&l+r)
    {
        memset(dp,-1,sizeof(dp));
        printf("%d\n",solve(r)-solve(l-1));
    }
    return 0;
}