深搜之剪枝优化（未完成）

剪枝的原则

1. 正确性
2. 准确性
3. 高效性

优化技巧

1. 优化搜索顺序
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 记忆化

例题:

---

数的划分

题目链接：P1025 数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

问有多少种不同的分法。

输入格式

n,k (6<n≤200，2≤k≤6)

输出格式

11个整数，即不同的分法。

输入输出样例

输入 #1

7 3

输出 #1

4

说明/提示

四种分法为：
1,1,51,1,5;
1,2,41,2,4;
1,3,31,3,3;
2,2,32,2,3.

题解：

这题就是普通的深搜，加上一些优化就能过

AC代码：

/*
* ===============================================
* Filename: divide.cpp
* Description: 
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];

int n, m, s = 0;

void dfs(int k)
{
    if (n == 0) return ;
    // 当剩余的数不足的时候终止搜索
    
    if (k == m)
    {
        // 能保证可以升序，答案加一
        if (n >= a[k - 1])
        {
            s++;
        }
        return ;
    }
    // 因为要保持升序，并且要上限尽可能低，下限尽可能高
    // 经过简单推算可知道上限最低是到剩余的数字的平均值，即n/(m-k+1)
    // 下限就是保持这个数列递增就行， 即a[k-1]
    for (int i = a[k - 1]; i <= n / (m - k + 1); i++)
    {
        a[k] = i;
        n -= i;
        dfs(k + 1);
        n += i;
        // 有借有还
    }
}

int main()
{
    cin >> n >> m;
    a[0] = 1;
    dfs(1);
    cout << s << endl;
    return 0;
}

---

若未经特殊说明，本文：《 深搜之剪枝优化（未完成） 》为博主原创作品，未经授权禁止转载