题目描述：
给你一个正整数 n ，请你返回 n 的 惩罚数 。
n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
1 <= i <= ni * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。
数据范围：
$1\le n \le 1000$
题解：
首先可以直接预处理出所有的数是不是惩罚数，预处理的过程中累加，后面直接读数组即可。
如果check一个数是不是惩罚数，需要使用回溯。
假设当前剩余的数为 $sum$ ，目标值为 $target$ 。
每次从 $sum$ 中拆出来一部分 $tmp$ ，看一看 $sum$ 剩余的与 $target - tmp$ 能否凑出来。
可以对 $sum$ 从后往前拆，拆出来一位，两位，三位等。设置 $mod = 10$ ， $tmp = sum % mod$ ，剩余的数为 $sum / mod$ ，每次对 $mod \times 10$ 。
代码：
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
50
51
52
53
54
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
vector<int> ret;
bool dfs(int sum, int target)
{
if (sum == target)
return true;
if (sum < target)
return false;
int tmp = 0;
int d = 10;
while (sum % d <= target)
{
tmp = sum % d;
if (dfs(sum / d, target - tmp))
{
return true;
}
d *= 10;
}
return false;
}
auto init = []()
{
int sum = 0;
ret.resize(1001);
for (int i = 1; i <= 1000; ++i)
{
int tmp = i * i;
if (dfs(i * i, i))
{
sum += i * i;
}
ret[i] = sum;
}
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int punishmentNumber(int n)
{
return ret[n];
}
};
|