[NOIP2001 提高组] 数的划分
题目描述
将整数 $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$.
【题目来源】
NOIP 2001 提高组第二题
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
/**************** 以下为快读 ****************/
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer in;
// 在没有其他输入时返回 null
static String next() {
try {
while (in == null || !in.hasMoreTokens())
in = new StringTokenizer(r.readLine());
return in.nextToken();
} catch (Exception e) {
}
return null;
}
static int nextInt() {
return Integer.parseInt(next());
}
static double nextDouble() {
return Double.parseDouble(next());
}
static long nextLong() {
return Long.parseLong(next());
}
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static final int N = 10;
static int n, k, cnt;
static int[] solute = new int[N];
static void dfs(int pos, int v, int sum) {//当前在选第pos个数 这个位置的数的大小从v开始
if(pos > k) {
int dsum = 0;
for(int i = 1;i < pos;i ++) {
dsum += solute[i];
}
if(dsum == n) cnt ++;
return;
}
for(int i = v;i <= n;i ++) {
solute[pos] = i;
if(sum + i > n) return;
dfs(pos + 1, i, sum + i);
solute[pos] = 0;
}
}
public static void main(String[] args) throws Exception{
n = nextInt();//整数k
k = nextInt();//k份
dfs(1, 1, 0);
out.print(cnt);
out.flush();
out.close();
}
}