LeetCode 2698. 2698. 求一个整数的惩罚数
原题链接
简单
作者:
Soel
,
2023-05-27 15:29:16
,
所有人可见
,
阅读 195
#pragma GCC otimize("O3")
#define LOCAL
int S[1010];
using i64 = long long;
int init = []() {
for (int i = 1; i <= 1000; i++) {
auto s = std::to_string(i * i);
int n = s.size();
std::function<bool(int, int)> dfs = [&](int p, int sum)->bool {
if (p == n) return sum == i;
int x = 0;
for (int j = p; j < n; j++) {
x = x * 10 + int(s[j] - '0');
if (dfs(j + 1, sum + x)) return true;
}
return false;
};
S[i] = S[i - 1] + (dfs(0, 0) ? i * i : 0);
}
return 0;
}();
class Solution {
using i64 = long long;
public:
int punishmentNumber(int n) {
return S[n];
}
};
#ifdef LOCAL
#define x first
#define y second
#elif LOCAL2
using namespace std;
using PII = pair<int, int>;
#endif