数位DP & BZOJ1026[SCOI 2009]windy数题解

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

数位DP

这个鬼东西是个啥????我咋没见过呢?
emmm……
数位DP,顾名思义,利用数字的每一个数位(个、十、百、千、万、……)来计算的动态规划算法。
啥?我还是不懂的?
那么我们还是来说一下这种算法的适用题型吧……
给定两个数a,b,求满足给定条件的数的个数。(举个栗子:求ab之间不包含子串“62”的数的个数)
这也太明显了吧……按照一个个把数字拆开检查不就行了么……
nope! 如果是a,b的范围是1 <= a,b <= 200000000001<=a,b<=20000000000呢?你还暴力拆开检查么?你家计算机跑上一天都不一定能跑出来。
那咋整?
数位DP!
数位DP的基本思路就是按照数位对数字进行拆开,但是数位DP会利用每一位的数进行动态规划从而达到消除重复计算的作用,从而减小时间复杂度。像是上面的例子,我们可以想象,其实我们计算很多数的时候是在进行一些不必要的重复计算的。而数位DP就是为了这类问题避开这些重复计算而被总结设计出来的。
下面我们来说一下数位DP的核心步骤。
枚举当前是第几位,然后枚举这一位上的数,再枚举这个的低一位的数,检查是否满足条件,进行状态转移。这一步的伪代码如下

void init(){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= 9;++i)
        dp[1][i] = 1;
    for(int i = 2;i <= 10;++i)
        for(int j = 0;j <= 9;++j)
            for(int k = 0;k <= 9;++k){
                if(满足题目条件)
                    dp[i][j] += dp[i-1][k];
            }
    return;
}

对数位DP数组计算完成后,对于题中的a,b,我们就只需要计算0——b中满足题目条件的数的个数和0——a-1中满足题目条件的个数,然后相减就可以得到我们想要的结果了。(差分前缀和的思想)一般来说这一步的代码是比较固定的,大致如下,具体题目自己调整。

long long solve(long long x){
    long long ans = 0;
    k = 0;
    memset(m,0,sizeof(m));
    if(x < 10)return x;
    while(x){
        m[++k] = x % 10;
        x /= 10;
    }
    for(int i = 1;i <= k-1;++i)
        for(int j = 1;j <= 9;++j)
            ans += dp[i][j];//这里是最高位为0的情况
    for(int i = 1;i < m[k];++i){
        ans += dp[k][i];//这是最高位不为0且未达到最高位最大限制的情况
    }
    for(int i = k-1;i >= 1;--i){
        for(int j = 0;j <= m[i] - 1;++j)
            if(满足条件)
                ans += dp[i][j];
        if(达到这一位最高限制的数不满足条件)
            break
        if(i == 1)
            ans += 1;
    }
    return ans;
}

可能有人注意到了最后一个i==1的条件,这是为什么呢?因为我们在枚举每一个数位上的数字时,我们总是要防止当前枚举的数大于我们一开始给定的数,所以我们是不会计算当前数位上放置可放置上限的情况的,对于最低位也是如此,这样就会少计算一种情况,即达到上限的这种情况。所以这里才会有这一种判断。 当然代码要根据不同题目来修改。
下面看一道例题:

[SCOI2009]windy数

Description

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

Input

两个数A,B

Output

A到B之间的windy数个数。

Sample Input

Sample 1:
1 10
Sample 2:
25 50

Sample Output

Sample 1:
9
Sample 2:
20

【数据规模和约定】

100%的数据,满足 1 <= A <= B <= 2000000000


题解:

典型的数位DP,条件就是相邻两位之间的差不小于2 那DP转移方程就是 dp[i][j] += dp[i-1][k];(其中abs(k-j) >= 2) 假如这个数有len位
统计答案时,我们先统计第len位内所有的比它第一位小的并且不是0的数的个数
然后我们枚举第len−1位到第1位的所有数 然后计算一下
然后这个时候第一位固定了 我们枚举剩下的位数 假如不合法 立刻退出
这里的细节,就是如果我们枚举到最低位的时候还存在windy数而没有立即跳出循环,我们需要在ans中+1。因为我们在对每一位的数枚举的时候,我们总是要考虑这一数位上的数的上限以防止多加,所以我们总是在枚举每一数位上的数的时候错过这一数位上的数的上限,最低位也是如此,但是最低位下面就没有数了,所以我们会少计算一个最低位的数达到上限的情况,所以我们要手动+1;
上代码!


代码

#include 
using namespace std;
typedef long long ll;
ll a,b;
ll dp[15][10];
int m[15];
int k;
void init(){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= 9;++i)
        dp[1][i] = 1;
    for(int i = 2;i <= 10;++i)
        for(int j = 0;j <= 9;++j)
            for(int k = 0;k <= 9;++k){
                if(abs(k - j) >= 2)
                    dp[i][j] += dp[i-1][k];
            }
    return;
}
long long solve(long long x){
    long long ans = 0;
    k = 0;
    memset(m,0,sizeof(m));
    if(x < 10)return x;
    while(x){
        m[++k] = x % 10;
        x /= 10;
    }
    for(int i = 1;i <= k-1;++i)
        for(int j = 1;j <= 9;++j)
            ans += dp[i][j];
    for(int i = 1;i < m[k];++i){
        ans += dp[k][i];
    }
    for(int i = k-1;i >= 1;--i){
        for(int j = 0;j <= m[i] - 1;++j)
            if(abs(j - m[i+1]) >= 2)
                ans += dp[i][j];
        if(abs(m[i] - m[i+1]) < 2)
            break;
        if(i == 1)
            ans += 1;
    }
    return ans;
}
int main(){
    init();
    cin >> a >> b;
    cout << solve(b) - solve(a-1) << endl;
    return 0;
}​
Pre: 三分法
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00