2015
04-16

# Machine scheduling

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 end with EOF.
Input will be four integers n,r,k,m.We assume that they are all between 1 and 1000.

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

5 2 3 2

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.


#include <iostream>

#define LL __int64
#define mod 1000000007

using namespace std;

const int N=1000;
LL s[N+5][N+5],c[2*N+5][2*N+5];

void cpre()
{
c[0][0]=1;
int i,j;
for (i=1;i<=2*N;i++)
for (j=0;j<=i;j++)
if (j>(i+1)/2) c[i][j]=c[i][i-j];
else if (j==0) c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

void spre()
{
int i,j;
s[0][0]=1;
for (i=1;i<=N;i++)
for (j=0;j<=i;j++)
if (i==j) s[i][j]=1;
else if (j==0) s[i][j]=0;
else s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%mod;
}

int main()
{
int n,r,k,m,i;
cpre();
spre();
while (scanf("%d%d%d%d",&n,&r,&k,&m)!=EOF)
{
LL res,s1=0;
int e=n-(r-1)*k-1;
if (e<0)
{
printf("0\n");
continue;
}
res=c[e+r][r];
for (i=0;i<=m;i++) s1=(s1+s[r][i])%mod;
res=(res*s1)%mod;
printf("%d\n",res);
}
return 0;
}


1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

2. #include <cstdio>

int main() {