算法介绍

这是一类形式比较固定的DP问题，往往是求在某个区间 [A, B] 中满足特定条件数的个数。做法基本上是下面的一套模板。

// 计算 0 - x 内有多少满足条件的数
int dp(int x) {
    // 0 特判
    if(!x) return 0;
    // 记录数字x的各位上的数字
    vector<int> nums;
	// B 为对应进制，通常是10进制下的问题
    while(x) nums.push_back(x % B), x /= B;
    // 最终答案
    int res = 0;
    // 上一位数的状态
    int last = 0;
    for(int i=nums.size()-1;i>=0;i--) {
        int t = nums[i];
      	// do sth.
        if(!i) {
            // do sth.
        }
    }
    return res;
}

通常，对于 i 位上的数字 k , [0, k-1上的状态我们可以通过诸如区间DP方式求出来。

例题讲解

AcWing 1081. 度的数量

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

using namespace std;

typedef long long LL;

const int N = 32;
LL f[N][N];
int X, Y, K, B;

int dp(int x) {
    if (!x) return 0;
    vector<int> nums;
    while (x) nums.push_back(x % B), x /= B;
    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int t = nums[i];
        if (t != 0) {
            if (t > 1) {
                res += f[i + 1][K - last];
                break;
            } else {
                res += f[i][K - last];
                last++;
                if (last > K) break;
            }
        }
        if (!i && last == K) res++;
    }
    return res;
}

int main() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) f[i][j] = 1;
            else f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
        }
    }
    cin >> X >> Y >> K >> B;

    cout << dp(Y) - dp(X - 1) << endl;
    return 0;
}

####AcWing 1082. 数字游戏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>

using namespace std;

int a, b;

const int N = 12;

int f[N][N];

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

int dp(int x) {
    if (!x) return 1;
    vector<int> nums;
    while (x) nums.push_back(x % 10), x /= 10;
    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int k = nums[i];
        if (last > k) break;
        for (int j = last; j < k; j++) {
            res += f[j][i + 1];
        }
        last = k;
        if (!i) res++;
    }
    return res;
}

int main() {
    init();
    // cout << f[2][2] << endl;
    while (cin >> a >> b) {
        cout << dp(b) - dp(a - 1) << endl;
    }
    return 0;
}

AcWing 1083. Windy数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>

using namespace std;

int a, b;

const int N = 12;

int f[N][N], g[N][N];

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

int dp(int x) {
    if (x >= 0 && x <= 9) return x + 1;
    vector<int> nums;
    while (x) nums.push_back(x % 10), x /= 10;
    int res = 0, last = -2;
    bool flag = false;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int k = nums[i];
        if(k != 0) {
            if (!flag) {
                res += g[0][i + 1];
            } else if (abs(last) >= 2) {
                res += f[0][i + 1];
            }
            for (int j = 1; j < k; j++) {
                if (abs(last - j) >= 2) {
                    res += f[j][i + 1];
                }
            }
        }
        if (abs(last - k) <= 1) break;
        last = k;
        if (k != 0) flag = true;
        if (!i) res++;
    }
    return res;
}

int main() {
    init();
    cin >> a >> b;
    cout << dp(b) - dp(a - 1) << endl;
    return 0;
}

####AcWing 1084. 数字游戏 II

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>

using namespace std;

int a, b;

const int N = 12;

int f[N][N][105];
int mod;

void init() {
    for (int len = 1; len < N; len++) {
        for (int i = 0; i <= 9; i++) {
            if (len == 1) {
                f[i][len][i % mod] = 1;
                continue;
            }
            for (int j = 0; j < mod; j++) {
                for (int k = 0; k <= 9; k++) {
                    f[i][len][j] += f[k][len - 1][((j - i) % mod + mod) % mod];
                }
            }
        }
    }
}

int dp(int n) {
    if (!n) return 1;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;
    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; i--) {
        int k = nums[i];
        for (int j = 0; j < k; j++) {
            res += f[j][i + 1][((mod - last) % mod + mod) % mod];
        }
        last = (last + k) % mod;
        if (!n && last % mod == 0) res++;
    }
    return res;
}

int main() {
    while (cin >> a >> b >> mod) {
        memset(f, 0, sizeof(f));
        init();
        cout << dp(b) - dp(a - 1) << endl;
    }
    return 0;
}

####AcWing 1085. 不要62

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12;

int f[N][N];

void init() {
    for (int len = 1; len < N; len++) {
        for (int i = 0; i <= 9; i++) {
            if (i == 4) continue;
            if (len == 1) f[i][len] = 1;
            else {
                if (i == 6)
                    for (int j = 0; j <= 9; j++) {
                        if (j == 2 || j== 4) continue;
                        f[i][len] += f[j][len - 1];
                    }
                else {
                    for (int j = 0; j <= 9; j++) {
                        if(j == 4) continue;
                        f[i][len] += f[j][len - 1];
                    }
                }
            }
        }
    }
}

int n, m;

int dp(int x) {
    if (!x) return 1;
    vector<int> nums;
    while (x) nums.push_back(x % 10), x /= 10;
    int last = 0, res = 0;
    // res += f[0][nums.size()];
    for (int i = nums.size() - 1; i >= 0; i--) {
        int t = nums[i];
        for (int j = 0; j < t; j++) {
            // if(i ==  nums.size() - 1&& j == 0) continue;
            if(last == 6 && j == 2) continue;
            if(j == 4) continue;
            res += f[j][i+1];
        }
        if(t == 4) break;
        if(last == 6 && t == 2) break;
        last = t;
        if(!i) res++;
    }
    return res;
}

int main() {
    init();
    while (cin >> n >> m, !(n == 0 && m == 0)) {
        cout << dp(m) - dp(n - 1) << endl;
    }
    return 0;
}