洛谷P1025 数的划分 DFS（在循环边界上下手）
up 主视频链接：https://www.bilibili.com/video/BV1vy4y1Z7b2/?spm_id_from=333.1007.0.0
题目链接： NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目如下：
[NOIP2001 提高组] 数的划分
题目描述
将整数
n
n
n 分成
k
k
k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：
n
=
7
n=7
n=7，
k
=
3
k=3
k=3，下面三种分法被认为是相同的。
1
,
1
,
5
1,1,5
1,1,5;
1
,
5
,
1
1,5,1
1,5,1;
5
,
1
,
1
5,1,1
5,1,1.
问有多少种不同的分法。
输入格式
n
,
k
n,k
n,k （
6
<
n
≤
200
6 6 2 ≤ k ≤ 6 2 \le k \le 6 2≤k≤6） 输出格式 1 1 1 个整数，即不同的分法。 样例 #1 样例输入 #1 7 3 样例输出 #1 4 提示 四种分法为： 1 , 1 , 5 1,1,5 1,1,5; 1 , 2 , 4 1,2,4 1,2,4; 1 , 3 , 3 1,3,3 1,3,3; 2 , 2 , 3 2,2,3 2,2,3. 【题目来源】 NOIP 2001 提高组第二题 初看此题——嗯，很简单的 dfs，直接上手写： void dfs(int x,int pre) // x表示枚举到第几位，pre表示前(x-1)个数字之和 { if(x==k){ cnt++; arr[x]=n-pre; for(int i=1;i<=k;++i) cout< cout< return ; } for(int i=1;i<=n-pre;++i) { arr[x]=i; dfs(x+1,pre+i); arr[x]=0; } } 结果毫无疑问地，连测试用例都过不去。 输出结果见下： 1 1 5 1 2 4 1 3 3 1 4 2 1 5 1 1 6 0 2 1 4 2 2 3 2 3 2 2 4 1 2 5 0 3 1 3 3 2 2 3 3 1 3 4 0 4 1 2 4 2 1 4 3 0 5 1 1 5 2 0 6 1 0 21 这里会有几个问题： 输出结果有0；重复输出。 对于存在 0 的，解决方法是剪枝，加入判断语句如下： if( n-pre < k-(x-1) ) return ; // eg. 6 1 _ n-pre=7-7=0 k-(x-1)=3-2=1 以 6 1 0 为例，枚举到第三位时，剩下可用的数为 n-pre=7-7=0 ，而剩下要填的位数为 k-(x-1)=3-2=1 位，而这些位置至少要填1，也就相当于必须要满足 (k-(x-1))*1 >= n-pre ，否则剪枝。 对于重复输出，我最开始想的是对最终答案除以 A(k,k) 即可，但也有问题： 比如 1 2 4 这三个数字的组合的确有 A(3,3)=6 个；但是 1 1 5 这三个数字的组合只有 3 个，如果还要再确定这两种情况分别有多少就更复杂了，没必要。 那么该怎么确保唯一性呢： 一种方法可以用 set（集合），但是我还不太会用（哭另一种方法就是确保单调不减（单调不增也可以），这样就需要记下前一个放入的数字是多少（用 arr[x] 记录第 x 位是多少，下一次枚举就从该数开始（for枚举的下界）。还有一个很重要的点：保证前 (k-1) 个数单调不减，但是最后一个数我是用 n-pre 确定的呀， n-pre 是有可能小于第 k-1 个数字的！——所以 for 上界也需要确定下来，是多少呢？ 我们目前的 for 是这样的： for(int i = arr[x-1] ; ; ++i ) // 注意为了达成这个 for，需要单独令 arr[0]=1 剩下数字为 n-pre，剩下位数为 k-x+1 我们枚举的第 x 位是剩下几位里最小的需要满足 i <= (n-pre)/(k-x+1) c++的整型除法使得会取到其 floor 值 于是最终的 dfs 函数代码如下： void dfs(int x,int pre) { if( n-pre < k-(x-1) ) return ; // 6 1 _ n-pre=7-7=0 k-(x-1)=3-2=1 if(x==k){ cnt++; arr[x]=n-pre; //这一步其实可以不要 return ; } for(int i=arr[x-1];i<=(n-pre)/(k-x+1);++i) { arr[x]=i; dfs(x+1,pre+i); arr[x]=0; } } 完整代码如下： #include using namespace std; const int N=201,K=7; int n,k,cnt; int arr[K]; void dfs(int x,int pre) { if( n-pre < k-(x-1) ) return ; // 6 1 _ n-pre=7-7=0 k-(x-1)=3-2=1 if(x==k){ cnt++; arr[x]=n-pre; //这一步其实可以不要 return ; } for(int i=arr[x-1];i<=(n-pre)/(k-x+1);++i) { arr[x]=i; dfs(x+1,pre+i); arr[x]=0; } } int main() { cin>>n>>k; arr[0]=1; dfs(1,0); cout< return 0; } 文章来源
发表评论