算法提高课第一章数位dp

减法求出区间答案，用树的思想来思考
关键在于预处理

1081. 度的数量 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 35;
int k, B;
int f[N][N];//从a个数里选b个数
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)//0--n
{
    if(!n) return 0;
    
    vector<int> nums;//把n拿出来
    while(n) nums.push_back(n % B), n /= B;
    //B进制下将n各位拿出来。
    
    int res = 0;//答案
    int last = 0;//前缀信息
    
    for(int i = nums.size() - 1; i >= 0; i-- )
    {
        int x = nums[i];
        //只能填0或者是1
        if(x)//求左边分支
        {
            res += f[i][k - last];//填0
            if(x > 1)
            {
                if(k - last - 1 >= 0) res += f[i][k - last - 1];//填1
                break;//不可能填大于1，所以右边没有分支了。
            }
            else
            {
                last ++;
                if(last > k) break;
            }
        }
        if(!i && last == k) res ++;//这是不能直接求的数也就是n本身
    }
    return res;
}
int main()
{
    init();  
    int l, r;
    cin >> l >> r;
    cin >> k >> B;
    cout << dp(r) - dp(l - 1);
}

1083. Windy数 - AcWing题库

需要考虑这几点

• 不加前导0的影响
• 算不算上0这个数
• $init$的含义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
//前导0不影响，因此需要特判有前导0的数
const int N = 15;
int f[N][N];//i个数，最高位j
void init()
{
    for(int i = 0; i <= 9; i ++ ) f[1][i] = 1;//预处理枚举的是包含前导0的数量
    
    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)
{
    if(!n) return 0;//排除0这个数
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    int res = 0, last = -2;
    for(int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for(int j = i == nums.size() - 1; j < x; j ++)//保证不包含前导0
        {
            if(abs(j - last) >= 2)
            res += f[i + 1][j];
        }
        if(abs(x - last) >= 2) last = x;
        else break;
        
        if(!i) res += 1;
    }
    //特判有前导0的情况
    for(int i = 1; i < nums.size(); i ++ )
    for(int j = 1; j <= 9; j ++ )
    {
        res += f[i][j];
    }
    return res;
}
int main()
{
    init();
    int a, b;
    cin >> a >> b;
    cout << dp(b) - dp(a - 1);
}

1084. 数字游戏 II - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 15, M = 110;
int f[N][10][M];
int p;
int mod(int x, int y)
{
    return (x % y + y) % y;
}
void init()
{
    memset(f, 0, sizeof 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;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for(int j = 0; j < x; j ++ )
            res += f[i + 1][j][mod(-last, p)];
            
        last += x;
        
        if(!i && last % p == 0) res ++;
    }
    return res;
}
int main()
{
    int a, b;
    while(cin >> a >> b >> p)
    {
        init();
        cout << dp(b) - dp(a - 1) << endl;
    }
}

1085. 不要62 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10;
int f[N][10];
void init()
{
    for(int i = 0; i <= 9; i ++ )
        if(i != 4) f[1][i] = 1;
    for(int i = 2; i < N; i ++ )
    for(int j = 0; j <= 9; j ++ )
    {
        if(j == 4) continue;
        for(int k = 0; k <= 9; k ++ )
        {
            if(k == 4 || j == 6 && k == 2) continue;
            f[i][j] += f[i - 1][k];
        }
    }
}
int dp(int n)
{
    if(!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n % 10), n /= 10;
    
    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for(int j = 0; j < x; j ++ )
        {
            if(j == 4) continue;
            if(j == 2 && last == 6) continue;
            res += f[i + 1][j];
        }
        if(x == 4 || last == 6 && x == 2) break;
        last = x;
        if(!i) res ++;
    }
    return res;
}
int main()
{
    init();
    int l, r;
    while(cin >> l >> r, l || r)
    {
        cout << dp(r) - dp(l - 1) << endl;
    }
}