http://acm.hdu.edu.cn/showproblem.php?pid=4045??

/************************************************************************************************************************************ ** 題意：給你n臺機器，選出r臺，每兩臺之間相差要大于等于k，然后r臺可以分成最多m組 ** 問有多少種方法。 ** 題解：首先從n里挑選r臺，r臺分成最多m組（Stirling第二類） 乘積即是答案； ** 個人比較弱 orz ACM_clove大牛：http://blog.csdn.net/acm_cxlove/article/details/7857785 ** 第一部分：首先每兩個機器之前至少有K-1個間隔，那么如果還剩余一些位置，則把這些多余的插入到R個機器中。 ** 那么剩余位置便是N-((R-1)*K+1),對于R個機器，R+1個位置， ** 接下來便是把N-((R-1)*K+1)分為R+1個集合(把r+1個空插入剩余的位置)，而且可以為空。 ** 做法是添加R+1個物品，然后用插板法，這樣保證 每一個集合都至少有一個， ** 然后再把每一個集合都減掉一個便是結果，最終結果便是C[n-((r-1)*k+1)+r+1-1][r]。應該比較好理解了。。。。。。 ** 第二部分：將R個元素最多分為M個集合，不為空的方案法。 ** 對于R個元素分為i個集合結果是第二類斯特林數，然后再統計合計一下就OK了 **************************************************************************************************************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; #define mod 1000000007 LL C[2005][2005]; LL stirling[2005][2005]; void init(){C[0][0] = 1;for(int i = 1;i <= 2000;i++){C[i][0] = C[i][i] = 1;for(int j = 1;j < i;j++){C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;}}stirling[0][0] = 1;for(int i = 1;i <= 1000;i++){stirling[i][i] = 1;for(int j = 1;j < i;j++)stirling[i][j] = (stirling[i-1][j-1] + j * stirling[i-1][j]) % mod;} } int main(){init();LL n,r,k,m;while(cin >> n >> r >> k >> m){if(n - (r-1) * k + 1 < 0) {cout << 0 << endl;continue;}LL sum = 0;for(int i = 1;i <= min(r,m);i++)sum = (sum + stirling[r][i]) % mod;LL ans = C[n - ((r-1) * k + 1) + r + 1 - 1][r] * sum % mod;cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的hdu-4045 Machine scheduling的全部內容，希望文章能夠幫你解決所遇到的問題。

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