首页 > ACM题库 > HDU-杭电 > HDU 4045-Machine scheduling-组合数学-[解题报告]HOJ
2015
04-16

HDU 4045-Machine scheduling-组合数学-[解题报告]HOJ

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.

题目大概意思就是说有n个机器,每天选择r个机器,这任意r个机器编号差不能<k,并且将它们分成不到m个相同的组,一共多少方案?

分两部分做,第一部分是把n个机器选择成r个机器。。但编号差不超过k如何处理?第二部分一看就是裸的斯特灵数。。两部分结果相乘为最后答案。

下面说第一部分,假设每个机器的编号差就是k,这样会出现一个空档,空当数为e=n-(r-1)*k-1,然后把这个空档分配到不同的区域中,r台机器有(r+1)个区域。。。根据插板法

的公式,就是C(e+r+1-1,e),即C(e,r),附代码:

#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;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/liverpippta/article/details/8043422


  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() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks