数字游戏II

标签：游戏 int res sum pos II 数字 include mod

数位DP

原题链接

题目描述：计算[l,r]之间各位数字之和MOD N == 0的数的个数

状态定义：
f[i][j]表示共有i位，且数字之和为j的数的总个数
设最高位为数字k，则状态转移：

\[f_{i,j}=\sum_{i=1}^9{f_{i-1},_{j-k}} \]

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

const int N = 15, M = 85;

int mod;
int f[N][M];

// 预处理
void init() {
    f[0][0] = 1;
    for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;
    for (int i = 2; i < N; i ++ )
        for (int j = 0; j < M; j ++ )
            for (int k = 0; k <= 9 && j - k >= 0; k ++ )
                f[i][j] += f[i - 1][j - k];
}

int cal(int n) {
    if (!n) return 0;
    
    std::vector<int> nums;
    while (n) nums.emplace_back(n % 10), n /= 10;
    
    int res = 0, sum = 0;
    for (int i = nums.size() - 1; i >= 0; i -- ) {
        int x = nums[i];
        for (int j = 0; j < x; j ++ )
            for (int k = mod; k - sum - j < M; k += mod)
                if (k - sum - j >= 0)
                    res += f[i][k - sum - j];
                    
        sum += x;
        if (!i && sum % mod == 0) res ++ ;
    }
    
    return res;
} 

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

记忆化搜索

#include <iostream>
#include <cstring>

const int N = 15, M = 150;

int a[N];
// f[i][j]表示共有i位数字，其总和为j的合法方案数
int f[N][M];
int mod;

// pos:当前第几位
// sum:当前所有数位的和
// limit:当前数是否有限制
int dfs(int pos, int sum, bool limit) {
    // 枚举到最后如果sum % mod == 0说明本身也是一种合法方案
    if (!pos) return sum % mod == 0; 
    if (!limit && ~f[pos][sum]) return f[pos][sum];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++ ) {
        res += dfs(pos - 1, sum + i, limit && i == up);
    }
    return limit ? res : f[pos][sum] = 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 >> mod) std::cout << cal(r) - cal(l - 1) << '\n';
    return 0;
}

标签：游戏,int,res,sum,pos,II,数字,include,mod
From： https://www.cnblogs.com/zjh-zjh/p/16709376.html