数位dp

2019-08-26 05:36:14来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

数位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]);//注意limit是要根据前几位更改所以要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>
#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]);//当有前导零时会对结果产生影响所以sta不会更改
        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));
}

 


原文链接:https://www.cnblogs.com/ninecities/p/11390441.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CodeForces 955D Scissors

下一篇:时间复杂度