SDNU 1029.巧分整数（斯特林数（改）dp）

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-9const 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

总结

以上是生活随笔为你收集整理的SDNU 1029.巧分整数（斯特林数（改）dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。