首页 > 代码库 > HDU 4045 Machine scheduling --第二类Strling数
HDU 4045 Machine scheduling --第二类Strling数
题意： n个数（1~n）取出r个数，取出的数相差要>=k， 然后分成m个可空组，问有多少种情况。
解法： 先看从n个数中取r个相差>=k的数的方法数，可以发现 dp[i][j] = dp[1][j-1] + dp[2][j-1] + ... + dp[i-k][j-1]，(dp[i][1] = i) 即维护一个前缀和即可，可以在O(r*n)内得出。
然后n个不同的数分成m个可以空的组，即为第二类Strling数的和 ： S[n][1] + S[n][2] + ... + S[n][m]。
S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1
边界条件：
S(p,p)=1 ,p>=0
S(p,0)=0 ,p>=1
然后 方案数为 ： S[n][1] + S[n][2] + ... + S[n][m]
然后两个结果相乘即可得出答案。
注意取模。
代码：
#include <cstdio>#include <iostream>#include <algorithm>#include <cstdlib>#include <cstring>#define Mod 1000000007#define lll __int64using namespace std;lll dp[1009][1009],sum[1009][1009];lll S[1009][1009];int main(){ int n,r,k,m; int i,j; for(i=1;i<=1000;i++) S[i][i] = 1, S[i][0] = 0; S[0][0] = 0; for(int p=1;p<=1000;p++) for(int k=1;k<=p-1;k++) S[p][k]=((k*S[p-1][k]%Mod+S[p-1][k-1])%Mod+Mod)%Mod; while(scanf("%d%d%d%d",&n,&r,&k,&m)!=EOF) { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++) { dp[i][1] = i, sum[i][1] = (sum[i-1][1] + dp[i][1])%Mod; dp[i][0] = 1, sum[i][0] = (sum[i-1][0] + dp[i][0])%Mod; } for(j=2;j<=r;j++) { for(i=k+1;i<=n;i++) { dp[i][j] = sum[i-k][j-1]%Mod; sum[i][j] = (sum[i-1][j] + dp[i][j])%Mod; } } lll ans=0; for(int i=1;i<=m;i++) ans+=S[r][i]; ans%=Mod; ans=ans*dp[n][r]; printf("%I64d\n",(ans%Mod+Mod)%Mod); } return 0;}
HDU 4045 Machine scheduling --第二类Strling数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。