dfs简单易懂--来自蒟蒻的题解

483 阅读 1 评论 0 点赞

# 欢迎各位赏脸来看本蒟蒻的题解 ~~保姆级教程~~（不是）
一眼dfs 但是可能会遇到重复加的问题 导致答案错误
##### 其实只要 思考一下dfs递归的本质 就会发现 只需要加一个 特判就可以完美的去重
##### 还有一个小技巧 如果从n开始 加一个数就减一个 就会让我们后面的判定简单很多
话不多说 直接上代码
###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long //个人习惯 被坑多了就习惯了
 
using namespace std;
int n;
int a[10010];
 
void dfs(int x , int now , int st) //x记录每次加的数 ， now记录当前还需要加的数 ， st记录数组下标 用于递归完后输出答案；
{
    if (now == 0)
    { 
        printf("%d=", n);      // =的位置需要注意 不要放在for里面了
        for (int i = 1 ; i < st - 1 ; i ++ )
        {
            printf ("%d+" , a[i]);       
        }
        printf("%d\n" , a[st - 1]);  //最后一个需要单独挑出来 不然会多出+号
    }
 
 
    for (int i = 1 ; i < n ; i ++ )
    {
        if (now - i >= 0 && i >= a[st - 1])	//重点 i >= a[st - 1] 特判处理上一个状态的数字 必须满足当前加的数 大于等于上一个数 即可完美去重 不需要使用哈希表去重 节约时间
        {
            a[st] = i; // 记录答案
            dfs(i , now - i , st + 1);  // 递归
        }
         
    }
}
signed main()
{
    cin>> n;
 
    dfs(0 , n , 1);   // 从n开始 记录为第一个位置
     
    return 0 ;
}
```

0.0分

4 人评分

本文分类：题解列表
浏览次数：483 次浏览
发布日期：2024-09-12 11:53:09
本文链接：https://blog.dotcpp.com/a/106337

上一篇 > 利用归并排序求逆序对--模版题
下一篇 > [信息学奥赛一本通T1678-Addition Chains]迭代加深？打表！

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

dfs简单易懂--来自蒟蒻的题解

评论列表共有 1 条评论

发表评论取消回复

dfs简单易懂--来自蒟蒻的题解

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 1 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 1 条评论

发表评论取消回复