MENU

深搜之剪枝优化(未完成)

September 22, 2020 • Read: 117 • 算法

剪枝的原则

  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;
}

Last Modified: September 29, 2020
Archives Tip
QR Code for this page
Tipping QR Code