不要62

标签：pre 不要 int res pos 62 include

数位DP

原题链接

题目描述：
计算[l, r]中不含数字62且不包含数字4的数的总个数

状态定义：
f[i][j]表示共有 i 位，且最高位为 j 的合法方案数
假设 k 为 j 后面的数字，则状态转移：

\[f_{i,j}=\sum_{k=0}^9{f{_{i-1},_k}},(j\neq4,k\neq4,jk不同时为62) \]

Code

#include <iostream>
#include <cstring>
#include <vector>

const int N = 15;

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; // 不合法状态直接continue
            for (int k = 0; k <= 9; k ++ ) {
                if (k == 4 || j == 6 && k == 2) continue;
                f[i][j] += f[i - 1][k];
            }
        }
}

int cal(int n) {
    if (!n) return 1;
    std::vector<int> nums;
    while (n) nums.emplace_back(n % 10), n /= 10;
    
    int res = 0, pre = 0;
    for (int i = nums.size() - 1; i >= 0; i -- ) {
        int x = nums[i];
        for (int j = 0; j < x; j ++ ) {
            if (j == 4 || pre == 6 && j == 2) continue;
            res += f[i + 1][j];
        }
        
        if (x == 4 || pre == 6 && x == 2) break; // 说明不存在右分支，直接break
        pre = x;
        
        if (!i) res ++ ;
    }
    
    return res;
}

int main() {
    init();
    
    int l, r;
    while (std::cin >> l >> r, l || r) 
        std::cout << cal(r) - cal(l - 1) << '\n';
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>

const int N = 15;

int a[N];
int f[N][N];

// pos:当前第几位
// pre:上一位是几
// limit:当前位是否有限制
int dfs(int pos, int pre, bool limit) {
    if (!pos) return 1;
    if (!limit && ~f[pos][pre]) return f[pos][pre];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++ ) {
        if (i == 4 || pre == 6 && i == 2) continue;
        res += dfs(pos - 1, i, limit && i == up);
    }
    return limit ? res : f[pos][pre] = res;
}

int cal(int n) {
    memset(f, -1, sizeof f);
    int len = 0;
    while (n) a[++ len] = n % 10, n /= 10;
    return dfs(len, 0, 1);
}

int main() {
    int l, r;
    while (std::cin >> l >> r, l || r) 
        std::cout << cal(r) - cal(l - 1) << '\n';
    return 0;
}

标签：pre,不要,int,res,pos,62,include
From： https://www.cnblogs.com/zjh-zjh/p/16711252.html