[CSP-J 2024] 小木棍题解记录

· · 个人记录

前言

说真的不知道为什么洛谷题解区都很难看懂，可能是我比较菜吧，这里提供一种非常简单的dp方法,我认为应该比洛谷题解区里的高赞dp题解要简单一些,另外本人是初一的小lj，所以表达能力可能有一点野鸡

思路

这里的dp不是主要用途而是辅助用途,我们设dp[i]为用i根木棍能拼出数字的最小位数,那么对于n个小木棍我们可以通过不断抽出木棍拼上一个最小且最优的最高位来达到全局最优解。而最优解其实就是拼上去以后不会因为用不起大的木棍数来减少位数而被迫用小的数字(木棍数)导致增加位数从而变大。那判断数j作为最高位是否是最优其实就是

dp[n] == dp[n - nums[j]] + 1 且 n>=j

dp[n]是n的最小位数，那dp[n-nums[j]]自然就是n根木棍减去数j需要的木棍数后的最小位数。因为我们是从小到大遍历j的(0~9),所以如果你抽出来一些木棍少可能导致后期还有余力无法花完木棍被迫增加位数从而不是正确的dp[n]所以说我们要的最优情况就是即使在用了这根也不会在后期被迫减少位数，也就是dp[n-nums[j]]加上用了的一位(1)是dp[n]的情况，我们只需要找到第一个这样的数即可因为是最小且最优的(j从小到大遍历)。最后还要记得前导零。
剩下的没什么好讲的了

code

以下是打了详细注释的代码

#include <bits/stdc++.h>
using namespace std;
int nums[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
constexpr int N = 1e5 + 7;
int dp[N], n;
//初始化，直接预处理
//dp[i]表示使用i根木棍的最少位数
void f()
{
    //初始化防止全是零
    //有些数可能用不完n根木棍他的dp值就是0x3f(无限)
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= 1e5; i++)
    {
        //看下最高位选什么
        //比较是选好还是不选好
        //如果选了那状态就变成了i-nums[j]了，在这个状态的最少位数再加1位然后0~9个数字都如此
        //即可得到dp[i]的正确解
        for (int j = 0; j < 10; j++)
        {
            if (i >= nums[j])
            {
                dp[i] = min(dp[i], dp[i - nums[j]] + 1);
            }
        }
    }
}
void solve()
{
    string s;
    //判断当前是不是在第一位(最高位)
    bool first = 1;
    while (n)
    {
        //从-1开始倒是后如果还是-1那就说明选不了了
        //PS:这里说的选不了其实就是还剩的n个木棍无法花出去了
        int cur = -1;
        for (int j = 0; j < 10; j++)
        {
            //因为数字是从小到大递增的所以找出第一个使用该数字且位数不变的数字就是最优的
            if (n >= nums[j] && dp[n] == dp[n - nums[j]] + 1)
            {
                //防止前导零
                if (j == 0 && first)
                    continue;
                //已经使用过了不会存在前导零
                first = 0;
                cur = j;
                break;
            }
        }
        //直接输出-1
        if (cur == -1)
        {
            cout << "-1\n";
            return;
        }
        //使用字符串来记录答案
        s += cur + '0';
        //减去当前这一位使用的数字的木棍需要数
        n -= nums[cur];
    }
    cout << s << '\n';
}
int main()
{
    f();
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        solve();
    }
    return 0;
}