算法day1 dfs搜索2题

一   火星人 

 拿到这种类似于排序的，这个就好比如我们之前学习dfs基础的时候里面的指数型枚举

指数型枚举	数据与数据之间没有任何枚举，就比如选这个数字与不选
组合型枚举	数据与数据之间有联系，下一个数字不可以给上一个数字
排列型枚举	数据与数据之间有联系，下一个数字比上一个数字加1

 所以我们刨析这个题目也就是这样我们以它的例子来讲解
也就是这样的一个排序方式
那我们这种，首先是每个数据与每个数据是有关系的，其次就是这个这个每次的对应的值都不可以给上一个，那么这种就是组合型枚举

我们就用之前所学过的组合型枚举来敲一遍代码

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=10010;
int m;           //手指数
int n;           //加的位数
int res=0;         //记录加的次数
int ans[N];      //答案寄存数组
int mas[N];      //火星人所给的数字
int st[N]={0};   //表示状态数
bool return0 = false;

void dfs(int x){
    if(return0 == true){
        return ;
    }
    
    if(x>m){
        res++;
        if(res==n+1){
            for(int i=1;i<=m;i++){
                printf("%d ",ans[i]);
            }
            return0 = true;
        }
        return;
    }
    
    for(int i=1;i<=m;i++){
        if(res==0){
            i=mas[x];
        }
        if(st[i]==0){
            ans[x]=i;
            st [i]=1;
            dfs(x+1);
            ans[x]=0;//清理现场
            st [i]=0;
        }
    }
}

int main(){
    scanf("%d",&m);
    scanf("%d",&n);
    for(int i=1;i<=m;i++){
        scanf("%d",&mas[i]);
    }
    dfs(1);
    return 0;
}

 我们这里写了一个减枝的操作前面的return0这个是用来减枝的，因为最后会有数据过不去

二  烤鸡

 我们来分析这个题目，这个题目是有很多的烤鸡的调料，然后有10种调料，这每个调料都是有对应的3个不同重量的，然后我们输入一个重量，然后剩下的调料的重量要等于这个重量
我们这里就是指数型枚举，3个重量都有选择或者不选择，但是这里一定要有10种调料的种类
 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 20;

int n;
int ret;
int ans[N];
int mem[59055][N];

void dfs(int x,int sum){
    if(sum>n) return;    //减枝
    
    if(x>10){
        if(sum==n){
            ret++;
        for(int i=1;i<=10;i++){
             mem[ret][i]=ans[i];
            }
        }
        return ;
    }
    
    for(int i=1;i<=3;i++){
        ans[x]=i;
        dfs(x+1,sum+i);
        ans[x]=0;
    }

}

int main(){
    scanf("%d",&n);
    dfs(1,0);
    printf("%d\n",ret);
    for(int i=1;i<=ret;i++){
        for(int j=1;j<=10;j++){
            printf("%d ",mem[i][j]);
        }
        printf("\n");
    }
    return 0;
}

 在计算指数型枚举的时候，我们的打印里面一定要有一个限制值，根据题目的不同来定，如果没有限制的话会进行重复的打印，有的题目是要求前面打印过之后后面不可以进行打印，有些是可以运行重复但是又限制条件

总结：

递归指数型枚举就是我们看题目的时候有选择或不选择的时候，一般都是指数型枚举，然后我们就要审题，题目如果有给限制条件的话，那么就是要利用限制条件来进行解决，如果没有的话就是要用到它当前的状态来决定，也就是状态数组

递归指数型枚举就是我们看到题目的时候，题目给我们有那种规律的，也就是类似于排序的，而且类似字典序的，一般就是要用到指数型枚举，但是这个一般都是前面用了那个数字，后面不许用，所以这个一般是要用到记忆数组的