Description
聪明的lg给syc出了一道简单的题目，syc把脑细胞都用光了也不知道该怎么去做，那么请厉害的你来帮助syc做做这道题目。题目的要求就是取一个整数n，这个整数n大于0小于等于200，然后把这个整数n分为k份，并且每一份不能为0，而且任意两种分法不能相同(不考虑顺序)。
例如：n=8,k=3, 下面三种分法被认为是相同的。
2，2，4； 4,2,2； 2,4,2；
问有多少种不同的分法。
Input
n，k (k<=n<=200，1<=k<=6)
Output
一个整数，即不同的分法。
Sample Input
8 3
Sample Output
5
Source
SDNU ACM-ICPC 2012省队选拔赛
思路：一开始想到了斯特林数，但是这个和斯特林数又不太一样，得剪枝
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-9
const int inf =
0x3f3f3f3f;
const int mod = 1e9+
7;
const int maxn =
100000 +
8;
int n, k, a[
1000 +
8][
1000 +
8];
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>
k;
memset(a, 0,
sizeof(a));
a[0][
0] =
1;
for(
int i =
1; i <= n; i++
)
for(
int j =
1; j <= k; j++
)
if(i >= j)
///剪枝
a[i][j] = a[i -
1][j -
1] + a[i -
j][j];
cout<<a[n][k]<<
'\n';
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11420349.html
相关资源：JAVA上百实例源码以及开源项目
