动态规划-数位Dp

作者: _NewMoon | 来源:发表于2020-07-01 23:20 被阅读0次

记录今天在Acwing学习的几道数位Dp题目，整理了思路，方便以后的复习：

1.度的数量

题目描述

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。

例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：

$17=2^4+2^0$
$18=2^4+2^1$
$20=2^4+2^2$

样例

输入
15 20
2
2

输出
3

数位DP

K个互不相同的B的整数次幂，等价于求数字num在B进制表示下是否是由K个1且其他位全是0组成，可用数位Dp来做。

对于数字num，存放其每一位上的数字(B进制表示下)，从高位向低位枚举，假设枚举到第i位，第i位上的数字是x，那么分以下几种情况讨论：

1.x == 0
那么第i位只能是0，后面数位上现在都不能确定，只能继续向后看.
2.x == 1
这里第i位可以分成两种情况：
- 1.第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
- 2.第i位放1，那么后面数位上的情况不能用组合数计算，因为要保证答案中的数字比原数字要小
3.x > 1
同样第i位分成两种情况
- 1.第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
- 2.第i位放1，那么后面的数位上可以放k-last-1个1，res += f[i][k-last-1];

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 34;

int f[N][N];  //组合数
int k,b;
int l,r;

void init(){
    for(int i = 0; i<N; i++)
        for(int j = 0; j<=i; j++)
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i-1][j-1] + f[i-1][j];
}

int dp(int n){
    int res = 0, last = 0;
    if(!n) return res;
    
    vector<int> a;
    while(n) a.push_back(n%b),n/=b;
    
    int len = a.size()-1;
    for(int i = len; i>=0; --i){
        int x = a[i];
        if(x){
            res += f[i][k-last];  //第i位放0，后i-1位放k-last个1(0~i-1位，所以第i位后面有i位)
            if(x>1){
                //第i位放1,后i-1位放k-last-1个1
                if(k-last-1>=0) res += f[i][k-last-1];
                break;  //这一位已经不合法了，所以上一步结束后直接break
            }else{
                //如果x为1，考虑到组成的数必须比原数字小，所以这里不能用组合数计算
                last++;
                if(last>k) break;  //1如果放完了，直接break
            }
        }
        if(!i && last == k) res ++;  //树的最右侧的分支
    }
    return res;
}
int main()
{
    init();  //预处理出组合数
    
    cin>>l>>r>>k>>b;
    cout<<dp(r) - dp(l-1);
    return 0;
}

2.windy数

题目描述

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。

Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？

数据范围

$1≤A≤B≤2×10^9$

样例

输入
1 10

输入
9

数位Dp

假设我们当前枚举到第i位(设共有n位)，且第i位上的数字为x，那么对于答案中第i位数字j来说，有两类：

1.0~x-1 (如果第i位是最高位，这里是1~x-1)
括号中提到的1~x-1后面会解释 ,我们用last记录上一位的数字，然后枚举j，如果abs(j-last) >= 2 就累加答案，res += f[i+1][j];
2.x
不需要枚举j，last = x,再枚举之后的数位即可

上述做完之后，由于上面的答案都是n位的，对于数位个数低于n的，再累加到答案中就行了

f数组的处理

f[i][j] 表示一共有i位，且最高位数字为j的满足windy数定义的数的个数

状态转移：因为第i位是j已经确定，考虑第i-1位，设第i-1位数字为k，那么根据windy数定义只要abs(k-j) >= 2就可以转移过来

$f[i][j] = \sum_{k=0}^{9}if(abs(k-j)>=2) f[i-1][k]$

关于前导0

上面提到了枚举的第i位是最高位，那么不能填0，这里解释一下，如果我们填0，那么答案就会加上f[i+1][0],，举这样一个例子，
对于数字13，他是满足windy数定义的，那么加上前导0之后的013就不会被f[3][0]加进去，原因就是abs(0-1)<2，这样就导致答案漏掉。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][N];  //f[i][j] 表示一共有i位，且最高为是数字j的满足wingy数定义的数的个数

void init(){
    for(int i = 0; i<=9; i++) f[1][i] = 1;
    for(int i = 2; i<=N; i++)
        for(int j = 0; j<=9; j++)
            for(int k = 0; k<=9; k++)
                if(abs(k-j)>=2) f[i][j] += f[i-1][k];
}

int dp(int n){
    int res = 0,last = -10;
    
    vector<int> a;
    while(n)a.push_back(n%10),n/=10;
    
    int len = a.size()-1;
    //答案是a.size()位的
    for(int i =len; i>=0; --i){
        int x = a[i];
        for(int j = (i==len); j<x; ++j)   //最高位从1开始
            if(abs(j-last)>=2) res += f[i+1][j];
            
        if(abs(x-last)<2) break;  //不满足定义，直接break
        last = x;
        
        if(!i) res ++;
    }
    //答案小于a.size()位的
    for(int i = 1; i<=len; i++)
        for(int j = 1; j<=9; j++)
            res += f[i][j];
    
    return res;
}
int main()
{
    init();
    int l,r;
    cin>>l>>r;
    cout<<dp(r)-dp(l-1);
    return 0;
}

3.数字游戏

题目描述

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。

现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

样例

输入
1 9
1 19
输出
9
18

数据范围

$1≤a≤b≤2^{31}−1$

数位DP

按照数位DP分析步骤：假设我们当前枚举到第i位，且第i位上的数字是x，那么现在对于答案的第i位数字j来说，可以填两类数字：

1.j取0~x-1
那么res += f[i+1][j];
2.j取x
last记录x，再枚举下一位

f数组

f[i][j] 表示一共有i位，且最高位数字为j的不降数的个数
状态转移：因为最高位已经固定，所以假设第i-1位是k，根据不降数定义k>=j,所以
$f[i][j] = \sum_{k=j}^{9}f[i-1][k]$

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12;
int f[N][N];  //f[i][j] 表示最高位是j且一共有i位的不降数的个数

void init(){
    for(int i = 0; i<=9; i++) f[1][i] = 1;
    for(int i = 2; i<=N; i++){
        for(int j = 0; j<=9; j++)
            for(int k = j; k<=9; k++)
                f[i][j] += f[i-1][k]; //f[i][j] = f[i-1][j] + f[i-1][j+1] + f[i-1][j+2] +...+ f[i-1][9];
    }
}

int dp(int n){
    if(!n) return 1;
    int res = 0,last = 0;
    
    vector<int> a;
    while(n) a.push_back(n%10),n/=10;
    int len = a.size()-1;
    
    for(int i = len; i>=0; --i){  //从高到低枚举
        int x = a[i];
        for(int j = last; j<x; j++)//last表示上一位数字大小,当前枚举的数字不能比last小(不降数定义)
            res += f[i+1][j]; //(0~i位，一共有i+1位)
            
        if(x<last) break;  //若小，则break
        last = x;  //更新last
        
        if(!i) res++;
    }
    return res;
}
int main()
{
    init();
    int l,r;
    while(cin>>l>>r) cout<<dp(r) - dp(l-1)<<endl;;
    return 0;
}

4.数字游戏Ⅱ

题目描述

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 $mod N$ 为 0。

现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。

数据范围

$1≤a,b≤2^{31}−1,$
$1≤N<100$

样例

输入
1 19 9

输出
2

数位DP

~~在几道数位Dp题目练习过后，这类题目重点在于找到左边那一类如何直接计算~~
对于这一题来说，假设我们当前枚举到的第i位，且第i位上的数字是x，那么对于答案中的第i位数字j来说，可以填两类数：

1.0~x-1
我们用last表示到当前为止，前面数位上的数字之和，对此，当前第i位数字为j，前面数字之和为last，那么
后i位(包括j这一位)数字之和sum与last的关系就是(last+sum)%N == 0,那么sum%N的结果等价于(-last)%N,
所以res += f[i+1][j][(-last%N)]; (后面会提到f数组的处理)
2.x
如果j填x，那么不用枚举了，last += x，再枚举下一位即可

f数组的处理

f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模N结果为k的数的个数

状态转移：因为第i位已经是j，且所有数字之和模N为k，所以我们考虑第i-1位，假设第i-1位数字是x，由于j已经知道，
那么剩下的i-1位数字之和模N的结果就是(k-j)%N，那么状态转移方程就是：

$f[i][j][k] = \sum_{k=0}^{N-1}\sum_{x=0}^{9} f[i-1][x][mod(k-j,N)]$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12, M = 102;

int f[N][10][M];  //f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模p位k的数字个数
int p;

int mod(int u,int v){
    return (u%v+v)%v;  //c++的%会得到负数，需要做一个偏移
}

void init(){
    memset(f,0,sizeof f);   //多组测试数据，f数组要清空
    for(int i = 0; i<=9; i++) f[1][i][i%p]++;
    
    for(int i = 2; i<N; i++)
        for(int j = 0; j<=9; j++)
            for(int k = 0; k<p; k++)
                for(int x = 0; x<=9; x++)
                    f[i][j][k] += f[i-1][x][mod(k-j,p)];
}

int dp(int n){
    if(!n) return 1;
    int res = 0,last = 0;
    
    vector<int> a;
    while(n) a.push_back(n%10),n/=10;
    
    int len = a.size()-1;
    for(int i = len; i>=0; --i){
        int x =a[i];    
        for(int j = 0; j<x; j++)  //第i位放0~x-1
            res += f[i+1][j][mod(-last,p)]; //0~i位，所以一共有i+1位
            
        last += x;
        if(!i && last % p == 0) res ++; 
    }
    return res;
}
int main()
{
    
    int l,r;
    while(cin>>l>>r>>p){
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }
    
    return 0;
}

动态规划-数位Dp

1.度的数量

题目描述

样例

数位DP

C++ 代码

2.windy数

题目描述

数据范围

样例

数位Dp

f数组的处理

关于前导0

C++ 代码

3.数字游戏

题目描述

样例

数据范围

数位DP

f数组

C++ 代码

4.数字游戏Ⅱ

题目描述

数据范围

样例

数位DP

f数组的处理

C++ 代码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划

算法