P11229 [CSP-J 2024] 小木棍

Quartz_Blocks · 2024-10-26 15:18:56 · 题解

CSP-J 2024 T3 DP Solution

看到很多朋友都是使用找规律解决此题的。这里给出一种 dp 的解法。

首先，我们先列出对于每一个数字，它需要多少木棒。

设 dp_i 为使用 i 根木棒所能够拼出的最小数字。

那我们可以人工推导出 dp 数组的 1 至 7 项

其中，由于 1 根木棒没有办法组成，记为 dp_1 = -1。由于不能出现前导 0，这里我们暂且将 dp_6 设为 6。

由于组成 1 个字符需要 2 至 7 根木棒，那么我们可以得出以下状态转移方程式：

其中，dp_1 至 dp_7 可以人工进行处理。

但是，前文提到我们将 dp_6 设为 6，所以我们需要特殊判断 i - j = 6 的情况。这种情况下，只需要在末尾加上 0 即可。

问题来了：数字太大 long long 也会炸，怎么处理？

那就需要请出高精度了。

我这里使用的是 string 模拟的高精度，注意 MLE!

由于这是 dp,且 dp_i 最多依赖到 dp_{i-7}，所以可以使用滚动数组。

于是就有了 AC 代码。

#include <bits/stdc++.h>
using namespace std;
//0 1 2 3 4 5 6 7 8 9
//6,2,5,5,4,5,6,3,7,6;
string sum[15] = {"-1","-1","1","7","4","2","6","8"};//预处理的 dp 前 7 位
string dp[15];
string mn(string x,string y){//比较大小
    if(x.length() != y.length()) return (x.length() > y.length() ? y : x);
    return x > y ? y : x;
}
string res[55];
int T,N[55],_N;
void solve(int n){
    dp[0] = dp[1] = "-1";
    for(int i = 2;i <= n;i++){
        dp[i%8] = "0";//初始化
        dp[i%8] = dp[(i-2+8)%8]+sum[2];//初始化
        if(i <= 7) dp[i] = sum[i];//对于较小的数字
        for(int j = i-2;j >= 0 && j >= i-7;j--){
            if(dp[j%8] != "-1") dp[i%8] = mn(dp[i%8],dp[j%8]+sum[i-j]);
            if(dp[j%8] != "-1" && dp[j%8] != "0" && i-j == 6) dp[i%8] = mn(dp[i%8],dp[j%8]+"0");
        }
        for(int j = 1;j <= T;j++){//循环数组需要即时记录答案
            if(N[j] == i) res[j] = dp[i%8];
        }
    }
}   

int main(){
    ios::sync_with_stdio(0);
    cin >> T;
    for(int i = 1;i <= T;i++){//优化，直接将 n 存进数组里，不用重复计算 dp
        cin >> N[i];
        _N = max(_N,N[i]);
    }

    solve(_N);
    for(int i = 1;i <= T;i++){
        if(res[i] == "") cout << "-1";//特殊情况 1
        cout << res[i] << endl;
    }

    return 0;
}

题外话：很遗憾赛时作者并没有使用滚动数组。

沉重悼念