数位dp介绍

2019/08/13 20:13
阅读数 61

不了解dp的可以先看一下dp

数位dp含义:

数位:一个数有个位,十位,百位,千位等等,数的每一位都是数位。

数位dp归为计数dp,是在数位上进行操作的dp。

数位dp的实质是一种快速枚举的方式,它满足dp的性质,然后进行记忆化搜索。

用途:

有两个数,两个数范围很大(例如1e9,甚至更大),求这两个数符合限定条件的个数。纯暴力不行,就要用数位dp。

例子:求从0到n,(n为2^32-1),(条件)求包含49的数有多少; 

思路or具体实现:

n为2^32-1,数位其实只有20位,枚举数位,就不会超时。

dp[shuwei][diaojian]。dp的第一维通常是数位,后面的几维根据题目条件来设定。上面给的例子只用了一维。

控制上界枚举,从最高位往下枚举。用记忆化搜索来做,抛开循环后转移状态能更加随意,大部分数位和动态规化的题都可随意切换。搜索与循环异曲同工之妙,但前者更易转移状态,在限制较多的情况下被大部分人喜爱。

例题:Bomb

思路 :数位dp=dfs+记忆化搜索。

需要注意上限即题目所给范围的预处理,本题用digtis[20] 数组,存储上限的数位,最好用一个函数来处理,比如solve(sum),处理时,对上限的数位总数拿一个变量进行存储,比如k或len。

在dfs中用 limit (有些题解是top)判定上限,dfs(len,条件,limit);

dfs执行数位dp,在搜索时用了 up_bound=(limit?digit[len]:9); 来标记上限,同时用cnt来存储满足的条件的数量,然后更新dp数组,更新时要满足if(!limit),到达上界,状态不完整。

在dfs中对条件的处理,需要根据题意去确定,每个题目不一样。

是否顶着上界,每层确定这一位选啥,判断是否和上一位冲突,全部确定完了方案数+1。

由于顶着上界是比较特殊的情况,所以这类答案直接一层层搜索出答案,不用记忆化,其他(不顶着上界)的情况用dp[][] 直接返回数量。

有些题目需要最后算一下最高位为0的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int digit[20]; //储存上界的每个数位 
LL dp[20][2];  //统计没有49的总数 

//if4它的上一位和当前位是否是4
//len 记录当前数位,从高位往下搜索 
//limit 上一位是否是上界 

LL dfs(int len, bool if4, bool limit){
    if(len==0) return 1ll;  //个位的时候,有一个分支。 
    if(!limit && dp[len][if4])  return dp[len][if4];
    //没到达上界并且数位已经统计过,直接返回数量。 
    
    LL cnt=0,up_bound=(limit?digit[len]:9);
    //标记数位的上界 
    
    //对整个数位进行记忆化搜索 
    for(int i=0;i<=up_bound;++i){
        if(if4&&i==9) continue;//碰到49不加入。
        cnt+=dfs( len-1, i==4,limit && i==up_bound);
        //向下搜索,判断上一位是否为4,上一位是否到达上界,当前位是否到上界。 
    } 
    if(!limit) dp[len][if4]=cnt; //到达上界是状态不完整,不更新dp 
    return cnt;//直接返回本次搜索结果,加入到最后结果中 
}

LL solve(LL num) //num是上界这个数 
{
    int k=0;//记录数位个数。
    while(num)
    {
        digit[++k]=num%10;
        num/=10; 
    } 
    return dfs(k,false,true); 
} 

int main(){
     int t;
    cin>>t;
    while(t--)
    {
        LL n;
        cin>>n;
        cout<<n+1-solve(n)<<endl;
    } 
    return 0;
}
数位dp详解

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部