个人博客传送锚点:https://www.acwing.com/blog/content/55495/
传送锚点:https://www.luogu.com.cn/problem/P1025
题目描述
将整数 $n$ 分成 $k$ 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。
例如:$n=7$,$k=3$,下面三种分法被认为是相同的。
$1,1,5$;
$1,5,1$;
$5,1,1$.
问有多少种不同的分法。
输入格式
$n,k$ ($6<n \le 200$,$2 \le k \le 6$)
输出格式
$1$ 个整数,即不同的分法。
样例 #1
样例输入 #1
7 3
样例输出 #1
4
提示
四种分法为:
$1,1,5$;
$1,2,4$;
$1,3,3$;
$2,2,3$.
思路
这题我们在for循环时还要在进行类似于剪枝优化,如果当前的和 + 剩下的几位数乘i大于n,剪掉就完事,即代码
for (int i = start; sum + i * (k - x + 1) <= n; i++)
中的sum + i * (k - x + 1) <= n
。
code
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
int n,k;
int res = 0;//存储方案数
void dfs(int x,int start,int sum) {//x代表当前数字,start代表遍历到第几位
if (x > k) {
if(sum == n){
res ++;
}
return;
}
for (int i = start; sum + i * (k - x + 1) <= n; i++) {//进行进一步剪枝优化
//k - x + 1为还要填的数字个数,
dfs(x+1, i,sum + i);
}
}
int main()
{
cin >> n >> k;
dfs(1, 1, 0);
cout << res;
return 0;
}
标签:NOIP2001,int,sum,样例,start,划分,include,提高,分法
From: https://www.cnblogs.com/6Luffy6/p/18196745