hdu 4045 Machine scheduling [ dp + 斯特林数]
Machine scheduling
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1048 Accepted Submission(s): 387
Input will be four integers n,r,k,m.We assume that they are all between 1 and 1000.
13083183 | 2015-03-10 19:16:25 | Accepted | 4045 | 358MS | 25380K | 1461 B | G++ | czy |
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <algorithm> 5 6 #define ll long long 7 int const N = 1005; 8 ll const mod = 1000000007; 9 10 using namespace std; 11 12 ll stl[N][N]; 13 ll sumstl; 14 ll n,r,k,m; 15 ll dp[N][N]; 16 ll sum[N][N]; 17 ll ans; 18 19 void ini1() 20 { 21 memset(stl,0,sizeof(stl)); 22 ll i; 23 for(i=1;i<=1000;i++){ 24 stl[i][i]=1; 25 } 26 stl[0][0]=1; 27 ll p,j; 28 for(p=1;p<=1000;p++){ 29 for(j=1;j<=p;j++){ 30 stl[p][j]= (j*stl[p-1][j]+stl[p-1][j-1])%mod; 31 } 32 } 33 34 //for(p=1;p<=10;p++){ 35 // for(j=1;j<=p;j++) printf(" p=%I64d j=%I64d stl=%I64d\n",p,j,stl[p][j]); 36 // } 37 } 38 39 void ini() 40 { 41 ll i; 42 sumstl=0; 43 for(i=1;i<=m;i++){ 44 sumstl=(sumstl+stl[r][i])%mod; 45 } 46 memset(dp,0,sizeof(dp)); 47 memset(sum,0,sizeof(sum)); 48 ans=0; 49 // printf(" sumstl=%I64d\n",sumstl); 50 } 51 52 void solve() 53 { 54 int i,j; 55 for(i=n;i>=1;i--){ 56 dp[i][1]=1; 57 sum[i][1]=(sum[i+1][1]+dp[i][1])%mod; 58 } 59 for(j=2;j<=r;j++){ 60 for(i=n-k;i>=1;i--){ 61 dp[i][j]=sum[i+k][j-1]; 62 sum[i][j]=(sum[i+1][j]+dp[i][j])%mod; 63 } 64 } 65 ans=(sum[1][r]*sumstl)%mod; 66 } 67 68 void out() 69 { 70 printf("%I64d\n",ans); 71 } 72 73 int main() 74 { 75 //freopen("data.in","r",stdin); 76 ini1(); 77 while(scanf("%I64d%I64d%I64d%I64d",&n,&r,&k,&m)!=EOF) 78 { 79 ini(); 80 solve(); 81 out(); 82 } 83 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。