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


Problem Description
A Baidu’s engineer needs to analyze and process large amount of data on machines every day. The machines are labeled from 1 to n. On each day, the engineer chooses r machines to process data. He allocates the r machines to no more than m groups ,and if the difference of 2 machines‘ labels are less than k,they can not work in the same day. Otherwise the two machines will not work properly. That is to say, the machines labeled with 1 and k+1 can work in the same day while those labeled with 1 and k should not work in the same day. Due to some unknown reasons, the engineer should not choose the allocation scheme the same as that on some previous day. otherwise all the machines need to be initialized again. As you know, the initialization will take a long time and a lot of efforts. Can you tell the engineer the maximum days that he can use these machines continuously without re-initialization.
 

 

Input
Input end with EOF.
Input will be four integers n,r,k,m.We assume that they are all between 1 and 1000.
 

 

Output
Output the maxmium days modulo 1000000007.
 

 

Sample Input
5 2 3 2
 

 

Sample Output
6
Hint
Sample input means you can choose 1 and 4,1 and 5,2 and 5 in the same day. And you can make the machines in the same group or in the different group. So you got 6 schemes. 1 and 4 in same group,1 and 4 in different groups. 1 and 5 in same group,1 and 5 in different groups. 2 and 5 in same group,2 and 5 in different groups. We assume 1 in a group and 4 in b group is the same as 1 in b group and 4 in a group.
 

 

Source
 

 

Recommend
lcy   |   We have carefully selected several similar problems for you:  4043 4047 4050 4048 4042 
 
题意:n个机器,每天选出r台,将其分成不超过m组,要求选出的机器之间编号之差>=k,每天的选择不能与之前相同,问最多能有多少天。
题解:
将r台机器分成不超过m组,可以用斯特林数进行预处理。下面就是求选出r台机器的方案数了。
然后dp[i][j]表示,选择编号i的机器,在[i,n]的区间里面需要选择j台机器的方案数。
sum[i][j]表示在[i,n]的区间里面需要选择j台机器的方案数。
那么转移方程为:
dp[i][j]=sum[i+k][j-1];
sum[i][j]=sum[i+1][j]+dp[i][j];

 

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 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。