【每日一题】Problem 538B. Quasi Binary

原题

解决思路

最简单的思路就是贪心了，每次生成不超过目标值的 \(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\) 个可以达到目的的最少数量