欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1149 火柴棒等式 (DFS)

程序员文章站 2024-03-24 16:19:28
...

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

P1149 火柴棒等式 (DFS)

  • 起初以为这个题需要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;
}
相关标签: # 洛谷