解题思路:
dfs简单使用。其中,需要对划分做一些简单处理,即升序划分。
注意事项:
本题解没有对dfs进行优化,时间复杂度较高,但是能过oj。
参考代码:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int k = 0; static int n = 0; static int res = 0; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] s = reader.readLine().split(" "); n = Integer.parseInt(s[0]);//整数n k = Integer.parseInt(s[1]);//被分成k份 if (n == 0 || k == 0 || n < k) return; dfs(0,0,1); System.out.println(res); } /** * @param sum 所分数之和 * @param cnt 所分成数的个数 * @param start 起始数(升序划分) */ static void dfs(int sum, int cnt, int start) { //cnt == k 时判断是否所划分的数为n if (cnt == k) { if (sum == n) { res++; } return; } //sum大于n时直接返回 if (sum > n) { return; } for (int i = start; n - sum >= i * (k - cnt); i++) { dfs(sum+i,cnt+1,i); } } }
0.0分
8 人评分
C语言程序设计教程(第三版)课后习题8.3 (Java代码)浏览:1369 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:1066 |
大小写转换 (C语言代码)浏览:844 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1307 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:590 |
C语言训练-求PI* (C语言代码)浏览:613 |
【绝对值排序】 (C语言代码)浏览:820 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:577 |
【偶数求和】 (C语言代码)浏览:431 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:636 |