火柴棒等式,暴力dfs

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 全局变量声明
int n, a[10005], b[10005] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int k = 0;
int ss(int x) {
    // 如果b数组中已经存在该数字的火柴棒数量，直接返回
    if (b[x] > 0) {
        return b[x];
    } else {
        int c = 0;
        // 计算数字x每一位的火柴棒数量并累加
        while (x) {
            c += b[x % 10];
            x /= 10;
        }
        return c;
    }
}

void dfs(int x, int y) {
    // 如果火柴棒数量超过n-4，则返回
    if (y > n - 4) {
        return;
    }
    // 如果处理到第4位，检查条件是否满足
    if (x > 3) {
        if (a[1] + a[2] == a[3] && y == n - 4) {
            k++;
        }
        return;
    }
    // 遍历所有可能的数字组合
    for (int i = 0; i <= 1000; i++) {
        a[x] = i;
        dfs(x + 1, y + ss(i)); // 递归调用下一层
        a[x] = 0; // 回溯
    }
}
int main() {
    cin >> n; // 输入火柴棒总数
    dfs(1, 0); // 开始深度优先搜索
    cout << k << endl; // 输出满足条件的方案数
    return 0;
}