题解：P1025 [NOIP2001 提高组] 数的划分

张开发
• 2026/4/10 3:58:27 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

题解：P1025 [NOIP2001 提高组] 数的划分
原文https://www.luogu.com.cn/article/8t3rqvj5 点个赞吧思路这不是 DFS 板子题吗实在没什么好讲的……还是讲讲吧。使用递归的方法来尝试所有可能的划分。每次递归处理一个部分将整数加入当前部分然后递归处理下一个部分。从最小的整数开始尝试将其加入当前部分。继续递归处理直到构建出k kk个部分。当所有k kk个部分都被填满时检查这些部分的整数和是否等于n nn。如果是将这种划分计入结果。为了确保不同顺序的相同划分只被计数一次规定每个部分中的整数必须不小于该部分之前的最小整数。这通过在递归调用中只尝试从当前整数开始及之后的整数来实现。剩下的在代码里讲吧。Code#includebits/stdc.husingnamespacestd;intn,k,ans;voiddfs(intl,intp,ints){//l:当前份中最小的整数p:当前已经划分的份数s:当前所有份数的整数和if(pk1){//已经划分了 k 份if(sn)ans;//增加答案return;//返回}for(intil;sin;i)dfs(i,p1,si);//一定要从 l 开始避免重复sin 是为了确保不会超过总和 n递归作用分别为成为下一份的最小可能值、进入下一份的划分、更新当前所有份的总和}intmain(){cinnk,dfs(1,1,0),coutans;}

更多文章