【洛谷】P1025 数的划分（搜索、剪枝）

【题目】

https://www.luogu.org/problem/P1025

标签：搜索、递推、剪枝

【思路】

这里采用递归的方法，为了确保出现的方案不重复，可以规定方案中后面的数大于或等于前面的数。

begin是上一个出现的数，初始化为1（表示第一个数从1开始）。

num代表当前还能分的数，初始是输入的需要划分的数n。

floors是层数（对于超过层数的搜索直接剪枝），初始是输入的需要划分的块数k。

循环的上限是num/floors，避免出现因前面的数过大而导致后面的数无法取的情况。

【代码】

#include <iostream> using namespace std; int result = 0; void dfs(int begin, int num, int floors) { if (floors == 0) { // 剪枝，超过k层的剪掉 return; } for (int i = begin; i <= num / floors; i++) { if (floors == 1 && num - i == 0) { // 第k层满足条件 result++; } else { dfs(i, num - i, floors - 1); } } } int main() { int n, k; cin >> n >> k; dfs(1, n, k); cout << result << endl; return 0; }