动态规划-数位DP

- 日理万妓 2022-11-25 11:58 147阅读 0赞

### 文章目录 ###

*  数位DP
 *  例题
 *   *  HDU-2089
     *   *  法一、递推公式
         *  法二、记忆化搜索
     *  HDU-3555
     *   *  法一
         *  法二

# 数位DP #

--------------------

**数位DP**是指对数字的「位」进行的与计数相关的DP，例如求数位之和，特定数字问题等。往往给定的区间很大很大，暴力会超时，复杂度要 O ( l o n g ( n ) ) O(long(n)) O(long(n))才能过。  
一般解题思路是用DP对「数位」进行操作，记录已算过的区间状态，用于后面快速筛选。

# 例题 #

--------------------

## HDU-2089 ##

[HDU-2089 不要62 ][HDU-2089 _62]

> **Problem Description**  
> 杭州人称那些傻乎乎粘嗒嗒的人为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

### 法一、递推公式 ###

**定义 d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\]表示 i i i位数中首位是 j j j的最大合法数量**，例如 d p \[ 4 \] \[ 2 \] dp\[4\]\[2\] dp\[4\]\[2\]表示首位是2的4位数，即2000~2999中符合要求的数有多少个。  
那怎么求 d p \[ 4 \] \[ 2 \] dp\[4\]\[2\] dp\[4\]\[2\]？计算首位数字2的后面3位数就好了，即计算000~999中符合要求的数，所以递推公式：

*   d p \[ i \] \[ j \] = ∑ k = 0 9 d p \[ i − 1 \] \[ k \] dp\[i\]\[j\]=\\sum\_\{k=0\}^9dp\[i-1\]\[k\] dp\[i\]\[j\]=∑k=09dp\[i−1\]\[k\]

此题中 j ≠ 4 & & ! ( j = 6 & & k = 2 ) j\\neq4 \\&\\&!(j=6\\&\\&k=2) j=4&&!(j=6&&k=2)

#include<bits/stdc++.h>
    using namespace std;
    int a[20];
    int dp[20][10];
    void init(){ 
        dp[0][0] = 1;
        for (int i = 1; i <= 7; i++)//题目交代7位数
            for (int j = 0; j <= 9; j++)
                for (int k = 0; k <= 9; ++k)
                    if (j != 4 && !(j == 6 && k == 2))
                        dp[i][j] += dp[i - 1][k];
    }
    int solve(int x){ 
        int pos = 0;
        int ans = 0;
        while (x) { 
            a[++pos] = x % 10;
            x /= 10;
        }
        a[pos + 1] = 0;
        for (int i = pos; i >= 1; i--){ //枚举位数
            for (int j = 0; j < a[i]; j++) { //枚举首位
                if (a[i + 1] != 6 || j != 2)
                    ans += dp[i][j];
            }
            if (a[i] == 4 || (a[i + 1] == 6 && a[i] == 2))
                break;  //只要含4或62后面的都不统计了
        }
        return ans;
    }
    int main() { 
        init();
        int n, m;
        while (~scanf("%d%d", &n, &m) && (n + m)) { 
            printf("%d\n", solve(m + 1) - solve(n));
        }
        return 0;
    }

### 法二、记忆化搜索 ###

**d p \[ p o s \] \[ s t a t e \] dp\[pos\]\[state\] dp\[pos\]\[state\]表示第 p o s pos pos位 s t a t e state state状态时的最大合法数量**， s t a t e state state取值0和1，表示前一位是否是6。  
 p o s pos pos表示下标位置，在 s o l v e ( ) solve() solve()取余数据后得到每一位数字，此时是倒序所以 p o s pos pos是n-1开始；  
 p r e pre pre表示前一位( p o s + 1 pos+1 pos\+1)的数值，初始-1；  
 s t a t e state state表示前一位是否是 6 6 6，初始 0 0 0；  
 l i m i t limit limit判断当前位数值是否最大值，比如输入12，首先枚举十位为0，递归个位此时 l i m i t limit limit置 f a l s e false false个位可以枚举0-9，同时更新dp；十位枚举到1时，递归个位此时 l i m i t limit limit置 t r u e true true个位只能枚举到2，所以不能用记忆，也不能写入dp。  
具体看代码。

#include<bits/stdc++.h>
    using namespace std;
    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 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 n, m;
        while (~scanf("%d%d", &n, &m) && (n + m)){ 
            memset(dp, -1, sizeof(dp));
            printf("%d\n", solve(m) - solve(n - 1));
        }
        return 0;
    }

## HDU-3555 ##

[HDU-3555 Bomb][]

> **Problem Description**  
> The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.  
> Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?  
> **Input**  
> The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.  
> The input terminates by end of file marker.  
> **Output**  
> For each test case, output an integer indicating the final points of the power.  
> **Sample Input**  
> 3  
> 1  
> 50  
> 500  
> **Sample Output**  
> 0  
> 1  
> 15  
> **Hint**  
> From 1 to 500, the numbers that include the sub-sequence “49” are “49”,“149”,“249”,“349”,“449”,“490”,“491”,“492”,“493”,“494”,“495”,“496”,“497”,“498”,“499”,  
> so the answer is 15.

求1-n有多少个含49的数，是上一题的反面，去不含49即可。

### 法一 ###

#include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    ll a[100];
    ll dp[100][10];
    void init() { 
        dp[0][0] = 1;
        for (int i = 1; i <= 63; i++)
            for (int j = 0; j <= 9; j++)
                for (int k = 0; k <= 9; ++k)
                    if (!(j == 4 && k == 9))
                        dp[i][j] += dp[i - 1][k];
    }
    ll solve(ll x) { 
        int pos = 0;
        ll ans = 0;
        while (x) { 
            a[++pos] = x % 10;
            x /= 10;
        }
        a[pos + 1] = 0;
        for (int i = pos; i >= 1; i--) { 
            for (int j = 0; j < a[i]; j++) { 
                if (a[i + 1] != 4 || j != 9)
                    ans += dp[i][j];
            }
            if (a[i + 1] == 4 && a[i] == 9)
                break;  
        }
        return ans;
    }
    int main() { 
        init();
        ll t, n;
        scanf("%lld", &t);
        while (t--) { 
            scanf("%lld", &n);
            printf("%lld\n", n + 1-solve(n + 1));
        }
        return 0;
    }

### 法二 ###

#include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    ll a[100];
    ll dp[100][2];
    ll dfs(int pos, int pre, int sta, bool limit) { 
        if (pos == -1)
            return 1;
        if (!limit && dp[pos][sta])
            return dp[pos][sta];
        int up = limit ? a[pos] : 9;
        ll temp = 0;
        for (int i = 0; i <= up; i++) { 
            if (pre == 4 && i == 9)
                continue;
            temp += dfs(pos - 1, i, i == 4, limit && i == a[pos]);
        }
        if (!limit)
            dp[pos][sta] = temp;
        return temp;
    }
    ll solve(ll x) { 
        int pos = 0;
        while (x) { 
            a[pos++] = x % 10;
            x /= 10;
        }
        return dfs(pos - 1, -1, 0, true);
    }
    int main() { 
        ll t, n;
        scanf("%lld", &t);
        while (t--) { 
            scanf("%lld", &n);
            memset(dp, 0, sizeof(dp));
            printf("%lld\n", n + 1 - solve(n));
        }
        return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[HDU-2089 _62]: https://vjudge.net/problem/HDU-2089
[HDU-3555 Bomb]: https://vjudge.net/problem/HDU-3555
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708