数位dp

基础

对于一类问题：求给定区间内，满足给定条件的数的个数。一般情况下，这类问题通常采用暴力枚举求解：

for(int i=l;i<=r;++i)
    if(right(i))    ++ans;

很显然，当给定区间过大时，无法直接用朴素的方法求解。而所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。此时我们就需要利用数位的性质，设计log级别复杂度的算法。

解决这类问题最基本的思想就是“逐位确定”，有时求解这类问题时还需要做预处理，而预处理的过程即可视作数位dp。

简单而言，数位dp就是在给定的区间内，利用限定条件，逐位暴力枚举的算法。

 

对于数位dp，可通过简单的分析进行了解。

我们假设给定一个r=312。对于数位dp的过程，也就是从最高位即百位起，顺次枚举0-9。

但是很显然，以百位3为例，枚举时数字最大不能超过3。同时当百位为3时，十位最大不能超过1；当百位为3，十位为1时，个位最大不能超过2。其他限定情况下也以此类推。所以在实际的运用中，需要用一个布尔变量limit记录这一情况。

另一方面，数位dp中，对于问题的求解，通常是：

printf("%d\n",solve(l)-solve(r-1));

所以不管左端点是多少，百位一定会枚举到0，可是这样前导零可能会影响计数（视题目而定），所以通常情况下还会用一个布尔变量lead记录具体情况。

lead和limit一样，当前面已经不存在前导零or最大值限定时，是不必再继续限定的。

这样就得到了数位dp最基本的模板：

int dfs(int pos,int sta,bool lead,bool limit)
//pos即枚举到的位数；sta起到记录作用，一般情况下是记录上一位的数值，也有可能根据题意记录如4的个数5的个数
//lead记录前导零；limit记录数值的限定
{
    if(pos==-1)    return 1;//也就是位数由大到小枚举退出的边界
    if(!limit&&!lead&&dp[pos][sta]!=-1)    return dp[pos][sta];//情况已经记录时返回，节省时间
    int up=limit?a[pos]:9,ans=0;//确定可枚举到的最大数
    for(int i=0;i<=up;++i)
    {
        //判断条件
    }
    if(!limit&&!lead) dp[pos][sta]=ans;//记忆化，存储节省时间
    return ans;
}

int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }//确定每一位的最大值限定
    return dfs(pos-1,-1,true,true);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",solve(b)-solve(a-1));
}

要注意的是，dfs的四个变量并不一定会用到，也有可能更多，视情况而定。

同时，solve中的拆分也可能是二进制的情况。

 

例题

例题1 scoi2009 windy数

比较典型的数位dp例题，要注意前导零的情况，可以直接套板子。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
int a[15],dp[15][15];

int dfs(int pos,int sta,bool lead,bool limit)
{
    if(pos==-1)    return 1;
    if(!limit&&!lead&&dp[pos][sta]!=-1)    return dp[pos][sta];
    int up=limit?a[pos]:9,ans=0;
    for(int i=0;i<=up;++i)
    {
        if(!lead&&abs(i-sta)<2)    continue;
        if(lead&&i==0)    ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]);
        else    ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]);
    }
    if(!limit&&!lead) dp[pos][sta]=ans;
    return ans;
}

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

int main()
{
    memset(dp,-1,sizeof(dp));
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",solve(b)-solve(a-1));
}

 

 

例题2 poj 3252 round numbers

这里就要注意sta存储的不再是上一位的值而是0比1多的值，但是因为可能会出现0比1少也就是负数的情况，而数组下标不能是负数，所以初始值就要根据题目设为32。

又因为是二进制，所以solve也会有一定的更改。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
int st,ed;
int a[35],dp[35][70];

int dfs(int pos,int sta,bool lead,bool limit)
{
    if(pos==-1)
        return sta>=32;
    if(!lead&&!limit&&dp[pos][sta]!=-1)
        return dp[pos][sta];
    int up=limit?a[pos]:1,ans=0;
    for(int i=0;i<=up;++i)
    {
        if(lead&&i==0)
            ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]);
        else
            ans+=dfs(pos-1,sta+(i==0?1:-1),lead&&i==0,limit&&i==a[pos]);
    }
    if(!lead&&!limit)
        dp[pos][sta]=ans;
    return ans;
}

int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x&1;
        x>>=1;
    }
    return dfs(pos-1,32,true,true);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&st,&ed);
    printf("%d",solve(ed)-solve(st-1));
    
    return 0;
}