Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解（数位dp)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解（数位dp)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

E -- Digit Sum Divisibl

题目大意：

思路解析:

代码实现：

E -- Digit Sum Divisibl

题目大意：

给你一个整数n，让你找出小于等于n的数中一共有多少个好整数，并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除，则称这个数为好整数。例如 12 能被 3 整除。

n<=10^14。

思路解析:

看到数位之和，应该优先想到数位dp，那么我们想到最大的数位之和应该为14*9=126。则我们可以枚举每个数位之和k，看0-n中间是否有数位之和加起来刚好是k，并且刚好能被k整除。所以我们遍历次数为 126 * 10^14，这是不能接受的，但是对于每一个k来说，其实当中有许多重复遍历情况，所以可以用记忆化搜索来加速遍历行为。文章来源地址https://www.toymoban.com/news/detail-793140.html

代码实现：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Main {
    static int[] dig = new int[15];
    static long[][][] dp;
    static int p;
    public static void main(String[] args) throws IOException {
         Scanner input = new Scanner(System.in);
         long n = input.nextLong();
         dp = new long[15][127][127];
         p = 0;
         while (n > 0){
             dig[p++] =(int) (n % 10);
             n /= 10;
         }
         long res = 0;
        for (int k = 1; k <= 126; k++) {
            for (int i = 0; i < 15; i++) {
                for (int j = 0; j < 127; j++) {
                    Arrays.fill(dp[i][j], -1);
                }
            }
            res += dfs(p - 1, 0, 0, k, false);
        }
        System.out.println(res);
    }
    // lim 表示当前位是否有限制，如果lim == false，表示当前位选择没有限制，可以选择 0-9，否则只能选择0-dig[u]
    // u 表示当前抉择到哪一位了‘
    // s 表示抉择到当前位的数位之和为多少，
    // t表示当前数模上k后的余数是多少
    public static long dfs(int u, int s, int t, int k, boolean lim){
        if (u == -1 && t == 0 && s == k) return 1;
        if (u == -1) return 0;
        if (lim && dp[u][s][t] != -1) return dp[u][s][t];
        int x = lim ? 9 : dig[u];
        long ans = 0;
        for (int i = 0; i <= x; i++) {
            ans += dfs(u - 1, s+i, (t * 10 + i) % k, k, i != x || lim);
        }
        if (lim) dp[u][s][t] = ans;
        return ans;
    }
}

到了这里，关于Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解（数位dp)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！