dfs-选数（c++）题解--NOIP2002

dfs-选数（c++）题解–NOIP2002

题目

#include
#include
#include
using namespace std;//深搜的题最好定义全局变量，因为dfs函数和主函数都会用到

int n,k;
int a[21];//定义一个存储所有可使用数字的数组
int book[21];//定义一个标记数组，用book是因为book在英文里有标记的意思，所以标记数组我经常用book
int b[21];//临时存储路径

int step;//定义步数，当步数比需求多的时候，深搜结束
int sum;//定义一个计数器
int num=0;//定义一个加和得到的结果
//c++里的全局变量会默认初始化为0，所以不管是否初始化，初值都是0

bool check(int x)//定义判断是否是素数的函数,是素数返回true，不是返回false
{
    if(x==1||x==2)
    return 1;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)return false;
    }
    return true;

}

void dfs(int step,int d)//定义深搜函数
{
    //判断深搜终止条件，这里是已经找出了k个数
    if(step==k+1)
    {   
        num=0;//将num重置
        for(int i=1;i<=k;i++)
        {
            num+=b[i];
        }
        if(check(num))
        {
            sum++;
        }
        return;
    }

    for(int i =d+1;i<=n;i++)//用d是为了优化时间复杂度，这样就可以每次不用从头遍历，只需要从下一个数字开始
    {
        if(book[i]==0)//如果这个数还没有被标记
        {
            book[i]=1;//进行标记，显示已经走过
            b[step]+=a[i];
            dfs(step+1,i);//开始走下一步
            book[i] =0;//撤消标记
        }
    }
    
}


int main()
{
    cin>>n;
    cin>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dfs(1,0);//从第一个节点（数组下标1）开始寻找，（因为存储的时候就是从1开始的0位置被空下来）
    cout<<sum;
    return 0;
}

还可以用dp做，典型的子集问题，用0-1背包的思路
如果有看不懂的地方可以在评论留言，看到就会回复的