NOIP 2008火柴棒等式题解（C++代码实现） 动态规划与枚举算法详解

一、题目解读

火柴棒等式问题（NOIP 2008，洛谷P1149）要求使用给定数量的火柴棒，构造形如 A + B = C 的等式，其中A、B、C均为整数，且火柴棒总数恰好等于输入值。需统计符合条件的等式数量。题目核心在于将数字拆解与火柴棒消耗建模为数学问题，寻找高效解法。

二、解题思路

采用枚举 + 火柴棒计数策略：

1. 映射关系构建：预计算0-9每个数字所需的火柴棒数量（如6根火柴构成“0”，2根构成“1”等），存储于match_count数组，降低重复计算开销。

2. 双层循环枚举A、B：限定A、B范围（0-1111）以避免溢出，计算C = A + B。

3. 总火柴棒计算：通过get_match_num函数累加A、B、C各自的火柴棒数，并额外计入“+”和“=”符号所需的4根火柴。

4. 匹配统计：若总火柴棒数等于输入n，则计数加1。

三、解题步骤

1. 初始化：定义输入n，计数器count，及火柴棒映射数组match_count。

2. 双层循环遍历A、B：

    外层循环A（0-1111），内层循环B（0-1111），确保组合覆盖所有可能。

3. 计算C及总火柴棒：

    通过C = A + B得到结果，调用get_match_num函数分别计算A、B、C的火柴棒数，并计入符号（+和=）的固定消耗。

4. 条件判断：若总火柴棒数等于n，则count++。

5. 输出结果：最终输出符合条件的等式数量。

四、代码与注释

#include <iostream>
using namespace std;

// 每个数字0-9所需的火柴棒数量
const int match_count[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

// 计算一个数字需要的火柴棒总数
int get_match_num(int num) {
    if (num == 0) return match_count[0];
    int total = 0;
    while (num > 0) {
        // 逐位累加火柴棒数（如123分解为1+2+3的火柴棒）
        total += match_count[num % 10];
        num /= 10;
    }
    return total;
}

int main() {
    int n;
    cin >> n;
    int count = 0;
    
    // 遍历所有可能的A和B组合
    for (int a = 0; a <= 1111; ++a) {
        for (int b = 0; b <= 1111; ++b) {
            int c = a + b;
            // 计算总火柴棒：A + B + C + '+' + '=' (符号需4根)
            int total = get_match_num(a) + get_match_num(b) + get_match_num(c) + 4;
            if (total == n) {
                count++;
            }
        }
    }
    
    cout << count << endl;
    return 0;
}

五、总结

该解法巧妙利用预计算与枚举结合，将火柴棒问题转化为数字拆解与累加。通过限定A、B范围避免无效计算，get_match_num函数优化了多位数字的火柴棒统计过程。尽管时间复杂度为O(n²)，但通过空间换时间的策略（静态数组）显著提升效率。对于算法竞赛中的资源限制场景，此思路具有普适性，可作为类似问题的基准解法。

来源：NOIP 2008火柴棒等式题解（C++代码实现） 动态规划与枚举算法详解