题目描述：
你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
数据范围：
$1\le lowLimit \le highLimit \le 10^5$
题解：
数位dp的话，可以求编号不超过多少的个位。这里需要求不超过上界，并且数位和为 $target$ 的个数。
因此需要求数位和为 $[1, 45]$ 所有 $target$ 的个数。每个都是需要前缀差。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
string s;
int len;
int dp[5][45];
int dfs(int step, int val, int target, bool isLimit)
{
if(step == len)
return val == target;
if(!isLimit && dp[step][val] != -1)
return dp[step][val];
int up = isLimit ? s[step] - '0' : 9;
int ans = 0;
for (int i = 0; i <= up; ++i)
{
ans += dfs(step + 1, val + i, target, isLimit && i == up);
}
if(!isLimit)
dp[step][val] = ans;
return ans;
}
int solve(int upper, int target)
{
memset(dp, -1, sizeof(dp));
s = to_string(upper);
len = s.length();
return dfs(0, 0, target, true);
}
int countBalls(int lowLimit, int highLimit)
{
int maxx = 0;
for (int i = 1; i <= 45; ++i)
{
maxx = max(maxx, solve(highLimit, i) - solve(lowLimit - 1, i));
}
return maxx;
}
};
|