DFS

递归

举个例子，将 $n$ 分解成 $k$ 个不同的正整数之和，输出所有方案（数字种类和顺序不同都可以）

暴力一点的方式是写 $k$ 重循环，枚举每个位置上的数字，但是如果 $k$ 是通过输入给定的，就不可行了。

我们可以先枚举第一个数字是多少，比如是$a[1]$，那么问题就变成了$n-a[1]$分解成$k-1$个不同的正整数之和

变成了一个类似的子问题，可以考虑用递归来实现：

int a[1001];//a数组负责存答案
int k;//一共要分解成k个数字
void dfs(int n,int k)//将n分解成k个数字之和
{
    if(k==0)//数字用完了
    {
        if(n==0)//分解完成
        {
            for(int i=1;i<=now;++i) cout<<a[i]<<' ';
            cout<<'\n';
        }
        return;
    }
    for(int i=1;i<=n;++i)//这个位置用的数字是多少
    {
        a[now]=i;
        dfs(n-i,k-1);//下一个位置，要分解的数字减小了i，个数减少了一个。
    }
}

回溯

加强一下刚才的例子：

将 $n$ 分解成 $k$ 个不同的正整数之和，但是不能有两个数字相同，输出所有方案（顺序不同可以）

除了枚举数字之余，还需要记录一下现在有哪些数字还没用到。

因为这个信息量比较大，所以用全局变量而不是局部变量来记录。

int a[1001];//a数组负责存答案
int k;//一共要分解成k个数字
bool vis[1001];// vis[i] 表示这个数字有没有被用过
void dfs(int n,int k)//将n分解成k个数字之和
{
    if(k==0)//数字用完了
    {
        if(n==0)//分解完成
        {
            for(int i=1;i<=now;++i) cout<<a[i]<<' ';
            cout<<'\n';
        }
        return;
    }
    for(int i=1;i<=n;++i) if(!vis[i])//这个数字还没被用过
    {
        vis[i]=1;
        a[now]=i;
        dfs(n-i,k-1);//下一个位置，要分解的数字减小了i，个数减少了一个。
        a[now]=0;
        vis[i]=0;//因为是全局变量，所以当我们选择下一个数字的时候，要把上一次选择的影响消除。
    }
}

减枝

$DFS$ 就像从一个初始状态出发，每个状态都可以到达若干不同的状态，像一颗开枝散叶的树。

（其实这个定义并不严格，因为有些状态会到达同一个节点，比如 $n$ 分解成 $k$ 个数字，前两个数字是 $2,2$ 和 $1,3$ 都会达到 $n-4$ 分解成$k-2$ 个数字的状态。）

所以，我们优化 $DFS$ 的时候，想办法让它少进入一些状态，来减少时间复杂度，把这个过程称为减枝。

记忆化

上面的例子中，前两个数选$2,2$和$1,3$都会进入同一个状态，我们称为$sta(n-4,k-2)$。

如果我们只计算方案数而不关心每个方案具体长什么样，那么就可以把$sta(n-4,k-2)$的答案给记录下来，第二次进入这个状态的时候直接返回。

因为有可能本来就是 $0$ 种方案，所以我们给没到过的状态标记为 $-1$ 。

int k;//一共要分解成k个数字
int dp[1010][1010];//记得全部初始化成 -1 
bool vis[1001];
int dfs(int n,int k)//将n分解成k个数字之和
{
    if(k==0)//已经有k个数字了
    {
        if(n==0) return 1;//分解完成，多了一种方案
        return 0;
    }
    if(dp[n][k]!=-1) return dp[n][k];
    int ans=0;
    for(int i=1;i<=n;++i) if(!vis[i])
    {
        vis[i]=1;
        ans+=dfs(n-i,k-1);//下一个位置，要分解的数字减小了i，个数减少了一个。
        vis[i]=0;
    }
    dp[n][k]=ans;
    return dp[n][k];
}

可行性剪枝

还是这个例子，在枚举这个位置用的数字是多少的时候，其实不用枚举到 $n$。

现在还需要分解成 $k$ 个数字，之后的 $k-1$ 个数字都需要至少为 $1$ ，所以第 $k$ 个数字最大只能是 $n-k+1$。

for(int i=1;i<=n-k+1;++i) if(!vis[i])
{
    vis[i]=1;
    ans+=dfs(n-i,k-1);//下一个位置，要分解的数字减小了i，个数减少了一个。
    vis[i]=0;
}

最优性剪枝

有的搜索题是要求答案的最小值，那么我们用一个全局变量记录现在已经找到的答案的最小值是多少。

如果现在状态的答案比已经搜到的最小值还大，就直接返回。

int ans=1e9;
void dfs(int now,int ret)//now是状态参数，ret是这个状态的答案
{
    if(ret>ans) return;//现在的答案比已经搜到的答案还要差，没必要再搜下去了，当然前提是这个ret不会再变小了！！！
    /*
    	继续搜索
    */
}

例题

生日蛋糕

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$（$1\le i\le M$）层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i<M$ 时，要求 $R_i>R_{i+1}$ 且 $H_i>H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S={\displaystyle \frac{Q}{\pi }}$ 最小。

（除 $Q$ 外，以上所有数据皆为正整数）。

样例输入输出

100
2

68

表面积可以表示成最底下一圈的原的面积加上所有层的侧面积，可以先枚举最底下是多大，然后在途中只计算侧面积。

可以直接考虑 dfs(now,v,ret,prer,preh)表示还剩 $now$ 层（从下往上），现在的体积是 $v$，现在的表面积是 $ret$，上一层的半径是 $prer$，上一层高度是 $preh$

int ans=1e9;
void dfs(int now,int v,int ret,int prer,preh)
{
    if(now==0)
    {
        if(v==n) ans=min(ans,ret);
        return;
    }
    for(int i=1;i<prer;++i)//要比上一层半径小，所以到pre-1为止。
    {
        for(int j=1;j<preh;++j)
        {
            dfs(now-1,v+j*i*i,ret+2*i*j,i,j);
        }
    }
}

for(int i=1;i<=n;++i)
{
	for(int j=1;j<=n;++j)//最地下一层的高度和半径直接枚举。
	{
		dfs(m-1,i*i*j,i*i+2*i*j,i,j);
	}
}

这样肯定会超时啦，想想怎么优化吧~

（一）可行性剪枝：

剩下 $now$ 层的体积至少是 $(1^3+2^3+3^3+\dots +no{w}^3)\pi$，（表面积 $i^2\pi$，高度 $i$），设为 $b[now]$ 如果 $v$ 加上 $b[now]$ 已经大于 $n$ 就无需继续搜索了。

剩下 $now$ 层半径和高度都要互不相同，所以第 $now$ 的半径和高度至少是 $now$，所以枚举的最小值应该是 $now$ 。

假设先枚举半径，再枚举高度，因为要保证后面的层数还能放下蛋糕，所以当半径是 $i$ 时，高度至多是

$$\frac{n-v-b[now-1]}{i^2}$$

（二）最优性剪枝：

如果还剩 $now$ 层，剩下的体积$V=(n-v)$，第 $i$ 层的侧面积为 $S_i$。

$$\begin{gathered} 2\ast V=\sum _{i=1}^{now}2\ast r_i\ast r_i\ast h_i=\sum _{i=1}^{now}{r}_i\ast S_i\le r_{now}\ast \sum _{i=1}^{now}{S}_i \\ \sum _{i=1}^{now}{S}_i\ge \frac{2V}{r_{now}} \end{gathered}$$

所以剩余的侧面积至少是 $\frac{2(n-v)}{prer}$，如果这个数字加上$ret$大于等于已经求出的表面积，则返回。

（三）改变枚举顺序：

如果我们从小到大去枚举半径和高度，那么对体积的削弱较小，后续可选择的方案更多。

如果从大到小去枚举，那么后续可选择的方案更少，节点状态数就会变少。

同时更容易早一步计算出一个当前的答案，最大化利用最优性剪枝。

int ans=1e9;
int n,m;
int b[21];
void dfs(int now,int v,int ret,int prer,int preh)
{
    if(now==0)
    {
        if(v==n) ans=min(ans,ret);
        return;
    }
    if(v+b[now]>n) return;//如果现在的体积加上剩下now层最少需要的体积大于n则返回
    
    if(ret+2*(n-v)/prer>=ans) return;//如果现在的表面积加上剩余now层最少的表面积大于等于ans则返回
    
    //从大到小枚举，减少搜索树枝条
    for(int i=prer-1;i>=now;--i)//要比上一层半径小，所以到pre-1为止。
    {
    	int h=min(preh-1,(n-v-b[now-1])/(i*i));//选择半径i的时候高度j的最大值
        for(int j=h;j>=now;--j)
        {
            dfs(now-1,v+j*i*i,ret+2*i*j,i,j);
        }
    }
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=20;++i)
	{
		b[i]=b[i-1]+i*i*i;//b[i]是剩下i层最少需要多少体积
	}
	for(int i=n;i>=m;--i)
	{
		int h=(n-b[m-1])/(i*i);
		for(int j=h;j>=m;--j)
		{
			dfs(m-1,i*i*j,i*i+2*i*j,i,j);
		}
	}
	cout<<ans<<'\n';
}

meet in middle

给定 $n$ 个数字，有多少种选择方式，使得选出的数字和大于 $m$ ？

$1\le n\le 40$，$1\le m\le {10}^9$。

显然每个数字有选或者不选两种情况，所以直接搜索的时间复杂度是 $O(2^{40})$。

将数字分成两组，前 $20$ 个数字一组，后 $20$ 个数字一组，然后对两组分别暴力枚举每个数字选或者不选：

每组的时间复杂度都是$O(2^{20})$ ，约等于 ${10}^6$。

将两组数字分别从小到大排序。

枚举其中一组数字，假如当前枚举到的数字是 $x$。

求另一组中有多少大于 $m-x$ 的数字，可以直接在另一组上二分。

时间复杂度变成了 $O(2^{\frac{n}{2}}\ast lo{g}_2(2^{\frac{n}{2}}))=O(2^{\frac{n}{2}}n)$

练习题

P1706 全排列问题

P2404 自然数的拆分问题

P2392 kkksc03考前临时抱佛脚

P1219 [USACO1.5] 八皇后 Checker Challenge

P1784 数独

P1019 [NOIP2000 提高组] 单词接龙

P1731 [NOI1999] 生日蛋糕

P3067 [USACO12OPEN] Balanced Cow Subsets G

ABCDEF - ABCDEF

P1120 小木棍 （选做，剪枝程度非常变态）