剪枝的原则
- 正确性
- 准确性
- 高效性
优化技巧
- 优化搜索顺序
- 排除等效冗余
- 可行性剪枝
- 最优性剪枝
- 记忆化
例题:
数的划分
题目链接: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;
}
作者:NorthCity1984
出处:https://grimoire.cn/algorithm/dfs2.html
版权:本文《深搜之剪枝优化(未完成)》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/algorithm/dfs2.html
版权:本文《深搜之剪枝优化(未完成)》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任