P1149 火柴棒等式 （DFS）

https://www.luogu.com.cn/problem/P1149

• 起初以为这个题需要dfs，但是其实只需要一个2000x2000的循环就可以枚举出全部答案。
• 忘记了0需要特判一下

#include<iostream>
using namespace std;
int tot,n;
int s[11] = {6,2,5,5,4,5,6,3,7,6,0};
int match(int n)
{
    int total = 0;
    if(n == 0)
        return 6;//这里忘记了0啊，因为0在while中会直接报错
    while(n)
    {
        total+=s[n%10];
        n/=10;
    }
    return total;
}

int main()
{
    cin >>n;
    for(int i = 0;i < 2000;i++)
        for(int j = 0;j < 2000;j++)
            if(match(i)+match(j)+match(i+j)+4 == n)tot++;

    cout << tot;
}

大佬

DFS大发

#include <iostream>
using namespace std;
int x[1001] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, b[4];//初始定义0~9火柴棒个数， b数组存放每次可能的等式
int n, tot = 0;
void search(int l)//搜索
{
    int i;
    for(i = 0; i <= 999; ++i)
    {
        if(n - x[i] >= 0)//火柴棍还够
        {
            b[l] = i;//火柴棒数放入数组
            n = n - x[i];//在总数中减去火柴棒
            if(l == 3) 
            {
                if(b[1] + b[2] == b[3] && n == 0) tot++;//满足等式且火柴棒用完
            }
            else search(l + 1);//回溯
            n = n + x[i];//保存之前状态
        }
    }
}
int main()
{
    int i;
    cin >> n;
    n = n - 4;
    for(i = 10; i <= 999; ++i)
     x[i] = x[i / 10] + x[i % 10];//把2位数火柴棒， 3位数火柴棒放入数组， 理论上可达到11111111，但因为数据弱四位就过了
    search(1);
    cout << tot;
    return 0;
}