洛谷P1025 数的划分

迈不过友情╰ 2022-05-29 03:24 216阅读 0赞

## 题目描述 ##

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

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

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。

## 输入输出格式 ##

输入格式：

n，k (6<n<=200，2<=k<=6)

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

7 3

输出样例\#1： 复制

## 说明 ##

四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;

解法一：动归

参考题解：[https://www.luogu.org/blog/user59166/solution-p1025][https_www.luogu.org_blog_user59166_solution-p1025]

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    int f[201][8];
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int n, k;
    	cin >> n >> k;
    
    	/*
    	a.至少有一个盒子只有一个小球的情况数+b.没有一个盒子只有一个小球的情况数
    
    这样进行划分是因为这种分类可以使a和b都有能写出来的表达式：
    
    a.因为盒子不加区分，那么1的情况数与“将n-1个小球放到k-1个盒子中”的情况数一样
    
    b.没有一个盒子只有一个小球，那么把每个盒子中拿出来一个小球，对应的是“把(n-k)个小球放到k个盒子中的情况数”
    	*/
    	for (int i = 1; i <= n; i++)
    	{
    		f[i][1] = 1;
    	}
    
    	for (int i = 2; i <= n;i++)
    	for (int j = 1; j <= k; j++)
    	{
    
    		if (i >= j)
    		f[i][j] = f[i - 1][j - 1] + f[i - j][j];
    	}
    	cout << f[n][k];
    	return 0;
    }

解法二：dfs

参考题解：[https://www.luogu.org/blog/user50748/solution-p1025][https_www.luogu.org_blog_user50748_solution-p1025]

下面是两种不同的dfs写法

/*#include<iostream>
    using namespace std;
    int n, k;
    int dfs(int sum,int step,int now)
    {
    	int g = 0;
    	if (step == 1)
    		g = 1;
    	else
    	for (int i = now; i <= sum / step; i++)
    		g+=dfs(sum - i, step -1, i);
    	return g;
    }
    
    int main()
    {
    	
    	cin >> n >> k;
    	cout<<dfs(n, k, 1);
    	return 0;
    }*/
    
    #include<iostream>
    using namespace std;
    int n, k;
    int ans;
    void dfs(int sum, int step, int now)
    {
    	if (step == k&&sum >= now)
    	{
    		ans++;
    		return;
    	}
    	if (step == k) return;
    	for (int i = now; i <= sum; i++)
    		dfs(sum - i, step + 1, i);
    }
    
    int main()
    {
    
    	cin >> n >> k;
    	dfs(n, 1, 1);
    	cout << ans;
    	return 0;
    }

[https_www.luogu.org_blog_user59166_solution-p1025]: https://www.luogu.org/blog/user59166/solution-p1025
[https_www.luogu.org_blog_user50748_solution-p1025]: https://www.luogu.org/blog/user50748/solution-p1025