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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。