解决思路
最简单的思路就是贪心了，每次生成不超过目标值的 \(quasibinary\)，即可使最终数量最少
#include <bits/stdc++.h>
int quasibinary(int max)
{
int res = 0;
int p = 0;
while (max > 0) {
if (max % 10 > 0) {
res += int(pow(10, p));
}
max /= 10;
++p;
}
return res;
}
int main()
{
int n; std::cin >> n;
std::vector<int> res;
while (n > 0) {
int target = quasibinary(n);
n -= target;
res.push_back(target);
}
std::cout << res.size() << std::endl;
for (auto &v : res) {
std::cout << v << " ";
}
std::cout << "\n";
return 0;
}
其他解
可以考虑使用 dp，待补充
完全背包
\(dp[i][j]\) 指代当目标值为 \(j\) 时，当前值取 \(i\) 个可以达到目的的最少数量