OI

递归、深搜及其优化

  1. 函数

    1. 一组一起执行一个任务的语句。

      返回类型 函数名(参数类型1 参数名1,..,参数类型n 参数名n)
{
    //函数体
    return 返回值
}
//对于void函数，不存在返回值。

  2. 递归函数

    1. 自己调用自己的函数

      eg. 阶乘

      int fact(int n)
{
    if (n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

    2. 递归的一般形式

      int find(arg1, arg2...)
{
    if (特殊情况 or 边界条件)
    {
        // 处理
        return xxx;
    }
    // 递归操作；
    return xxx;
}
// 对于void函数，直接使用return;

    3. step型递归

      • 例题：天平平衡问题

        题目描述

        你有n个重量不同的砝码和一个天平，每个砝码可以放在左盘或者右盘或者不放。砝码重量为 $w_1,w_2,…,w_n$ ，问有多少种放置砝码的方式，使得天平平衡?（两边都不放任何砝码也算一种平衡方式）

        输入格式

        第 1 行，1 个正整数 $n$ 。 第 2 行，$n$ 个正整数 $w_1,w_2,…w_n$，以空格分隔。

        输出格式

        输出使得天平平衡的放置方案数。

        输入输出样例

        输入数据 1

        5
1 2 3 5 6

        输出数据 1

        13

        数据范围

        对于 $100%$ 的数据，满足 $1\leq n\leq13,1\leq w_i\leq100$。

      • AC Code

        // 20230712 @ Hydro.ac
#include <bits/stdc++.h>
using namespace std;
int n, w[20], ans;
void find(int p, int wl, int wr)
{
    if (p > n) // 边界条件：如果已经枚举到超过n了
    {
        if (wl == wr)
        {
            ans++; // 答案++
        }
        return;
    }
    // 三种情况分别枚举递归
    find(p + 1, wl + w[p], wr);
    find(p + 1, wl, wr + w[p]);
    find(p + 1, wl, wr);
		//这里的wl和wr也可以用全局变量写
		//在调用之前要记得wl+=w[p]，调用完要减回去。称作回溯操作。
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    find(1, 0, 0);
    cout << ans;
    return 0;
}

  3. 深度优先搜索 DFS

    1. 听起来好高大上
    2. 利用递归函数，枚举所有的情况找到答案。
    3. 剪枝
      1. 对于中途发现已经不可能的情况直接跳出这一部分搜索。

    • 例题：P2089 烤鸡

      烤鸡

      题目背景

      猪猪 Hanke 得到了一只鸡。

      题目描述

      猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。

      现在， Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

      输入格式

      一个正整数 $n$，表示美味程度。

      输出格式

      第一行，方案总数。

      第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。

      如果没有符合要求的方法，就只要在第一行输出一个 0。

      样例 #1

      样例输入 #1

      11

      样例输出 #1

      10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

      提示

      对于 100% 的数据，$n \leq 5000$。

    • AC Code

      //20230712 @ Hydro.ac
//不写注释了。我自己都不想再看一遍这代码。
#include<bits/stdc++.h>
using namespace std;
int n,counter=0,u[10000][15],u2[15];
void dfs(int p,int sum)
{
    if(p==10)
    {
        if(sum==n)
        {
            counter++;
            for(int i=0;i<10;i++)
            {
                u[counter][i]=u2[i];
            }

        }
        return;
    }
    for(int i=1;i<=3;i++)
    {
        u2[p]=i;
        dfs(p+1,sum+i);

    }
    return;
}
int main()
{

	cin>>n;
    dfs(0,0);
    cout<<counter<<endl;
    for(int i=1;i<=counter;i++)
    {
        for(int j=0;j<10;j++)
            cout<<u[i][j]<<" ";
        cout<<endl;
    }
	return 0;
}