首页 > 试题广场 >

工作方案

[编程题]工作方案
  • 热度指数：1768 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 150M，其他语言300M
  • 算法知识视频讲解
牛牛手中有s份工作需要完成,牛牛准备将工作分给三位员工。考虑到三位员工还有其他工作需要做,牛牛规定他们每人必须要参与的工作数量分别是a,b,c。
牛牛需要制定详细的工作方案,需要满足每份工作至少有一个人做,同一份工作可以由两个或者三个人共同参与。牛牛一下意识到可能的工作方案很多,牛牛需要你帮他计算一下一共有多少种不同的工作方案(对于两种方案,如果某份工作分配的人或者人数不一样就考虑为不一样的工作方案)。

对于输入样例,s = 3, a = 3, b = 1, c = 1
a要参与所有三份工作,b和c各自有三种选择,所以不同的工作方案是3 * 3 * 1= 9
如果s = 3, a = 1, b = 1, c = 1
相当于对三个员工做全排列,所以不同的工作方案是3 * 2 * 1 = 6

输入描述:
输入包括一行,一行包括4个正整数s,a,b,c(1 ≤ s ≤ 50, 1 ≤ a, b, c ≤ s),分别表示需要完成的工作份数,每个员工必须要参与的工作数量。


输出描述:
输出一个正整数,表示不同的方案种数,答案可能很大,输出答案对1000000007取模。
示例1

输入

3 3 1 1

输出

9
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

const int M = 1e9+7;

int main(){
    int n, a[3];
    scanf("%d", &n);
    for(int i=0;i<3;i++)
        scanf("%d", &a[i]);
    sort(a, a+3);
    long s=0, t;
    int dp[n+1][n+1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        dp[i][0] = 1;
        for(int j=1;j<=n;j++)
            dp[i][j] = (dp[i-1][j-1]+dp[i-1][j])%M;
    }
    int l = n - a[2];
    for(int i=0;i<=l;i++){
        if(i<=a[1] && l-i<=a[0]){
            t = dp[a[2]][a[1]-i] % M;
            t = (t * dp[l][i]) % M;
            t = (t * dp[n-(l-i)][a[0]-(l-i)]) % M;
            s = (s + t) % M;
        }
    }
    s = (s * dp[n][a[2]]) % M;
    printf("%ld\n", s);

    return 0;
}

发表于 2020-10-01 23:38:14 回复(0)
更多回答
绅士喵头像 绅士喵
排列组合。这道题不太好讲，我就随便用一组测试用例来简单说明一下，主要思路就是先给工作量大的分配，最后给工作量小的分配。

测试用例：50 43 12 3

a的工作量最大，所以先给a分配，即。还剩下7个工作，保证b和c分配将其分配。
b的工作量次大，接着给b分配。b的工作量分为p和q两部分，p是和a重合的部分，q是在当前剩下的7中分配的。
p
 q
 还未被分配的工作个数（不能大于c的工作量）
5
 7
 0
6
 6
 1
7
 5
 2
8
 4
 3
case1：在当前剩下的7个工作量中，有7个分配给b，那么b有5个工作和a重合。b分配完后，还有0个工作量没有被分配，c在50个中随便挑3个。

case2：在当前剩下的7个工作量中，有6个分配给b，那么b有6个工作和a重合。b分配完后，还有1个工作量没有被分配，c必须完成这1个工作，然后在其余49个中随便挑2个。

case3：在当前剩下的7个工作量中，有5个分配给b，那么b有7个工作和a重合。b分配完后，还有2个工作量没有被分配，c必须完成这2个工作，然后在其余48个中随便挑1个。

case4：在当前剩下的7个工作量中，有4个分配给b，那么b有8个工作和a重合。b分配完后，还有3个工作量没有被分配，c必须完成这3个工作。

最后结果即：
    （ + + + ）*

这道题要多次求，利用常规算法恐怕会超时，即使不超时，如果不做一些处理也不会得到正确结果，比如当k = 25时，25!已经超出了long int 的范围。所以建议用动态规划 https://blog.csdn.net/echo1214_xie/article/details/82109254 。 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 51

const int mod = 1000000007;

int main(int argc, char *argv[])
{
    int i, j, s, left, cnk[MAX][MAX];
    long int cnt, tmp;
    vector<int> work(3);
    
    cin >> s >> work[0] >> work[1] >> work[2];
    sort(work.begin(), work.end());//排序，保证work2最大，work0最小
    for (i = 1, cnk[0][0] = 1; i < MAX; i++) //动态规划求c(n,k)
    {
        cnk[i][0] = 1;
        for (j = 1; j < MAX; j++)
        {
            cnk[i][j] = (cnk[i - 1][j - 1] + cnk[i - 1][j]) % mod; //没有取余的话会溢出
        }
    }
    
    left = s - work[2]; //给工作量最大的分配后，剩余工作量
    for(i = 0, cnt = 0; i <= left; i++) //i是work1在left中分担的工作量
    {
        if(i <= work[1] && left - i <= work[0])//left - i是work0在left中分担的工作量
        {
            tmp = cnk[work[2]][work[1] - i] % mod; // 在work2中，有work[1] - i分配给work1
            tmp = (tmp * cnk[left][i]) % mod; // left中有i个分配给work1
            tmp = (tmp * cnk[s - (left - i)][work[0] - (left - i)]) % mod; // work0的随意挑选部分
            cnt = (cnt + tmp) % mod; //每个case求和
        }
        
    }
    cnt = (cnt * cnk[s][work[2]]) % mod; //求和后与最初的情况求积
    cout << cnt << endl;
    
    return 0;
}




发表于 2019-01-29 18:25:27 回复(0)
to_check头像 to_check 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int dp[55][55][55][55];  //dp[i][j][k][l]表示前i个任务 第一个人完成j件 第二个人完成k件 第三个人完成l件的方案数
int main(){
    int s,a,b,c;
    scanf("%d%d%d%d",&s,&a,&b,&c);
    dp[0][0][0][0] = 1;
    for(int i=1;i<=s;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=i;k++){
                for(int l=0;l<=i;l++){
                    if(j)(dp[i][j][k][l] += dp[i-1][j-1][k][l])%=mod;
                    if(k)(dp[i][j][k][l] += dp[i-1][j][k-1][l])%=mod;
                    if(l)(dp[i][j][k][l] += dp[i-1][j][k][l-1])%=mod;
                    if(j&&k)(dp[i][j][k][l] += dp[i-1][j-1][k-1][l])%=mod;
                    if(j&&l)(dp[i][j][k][l] += dp[i-1][j-1][k][l-1])%=mod;
                    if(k&&l)(dp[i][j][k][l] += dp[i-1][j][k-1][l-1])%=mod;
                    if(j&&k&&l)(dp[i][j][k][l] += dp[i-1][j-1][k-1][l-1])%=mod;
                }
            }
        }
    }
    printf("%d\n",dp[s][a][b][c]);
    return 0;
}

发表于 2019-06-25 18:07:03 回复(0)
只恐夜深花睡去头像 只恐夜深花睡去 
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        final int mod = 1000000007;
        try(Scanner in = new Scanner(System.in)){
            int s = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int cnt[][][][] = new int[51][51][51][51];
            cnt[0][0][0][0] = 1;
            for(int i = 1;i <= s; i++) {
                for(int j = 0;j <= i; j++) {
                    for(int k = 0; k <= i; k++) {
                        for(int l = 0; l <= i; l++) {
                            if(j != 0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j-1][k][l] % mod) % mod;
                            if(k != 0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j][k-1][l] % mod) % mod;
                            if(l != 0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j][k][l-1] % mod) % mod;
                            if(j!=0 && k!=0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j-1][k-1][l] % mod) % mod;
                            if(j!=0 && l!=0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod + cnt[i-1][j-1][k][l-1] % mod) % mod;
                            if(k!=0 && l!=0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j][k-1][l-1] % mod) % mod;
                            if(j!=0 && k!=0 && l!=0) cnt[i][j][k][l] = (cnt[i][j][k][l] % mod +  cnt[i-1][j-1][k-1][l-1] % mod) % mod;
                        }
                    }
                }
            }
            System.out.println(cnt[s][a][b][c]);
        }
    }

}

Java取模不能用左子式，所以看起来就有点难受。
思想是参考楼上to_check老哥C++,思想就是dp。
当工作量s + 1时候，这个1需要后面三个人来做，至少一个人做，所以2^3 - 1种情况，故而7条判断语句

发表于 2019-07-26 10:18:07 回复(0)
新书奇谭头像 新书奇谭
用容斥原理来做非常简单，用t[i]储存至少有i个任务没有人做的情况数，则最后方案数为t[0]-t[1]+t[2]-t[3]......C[i][j]用于存储组合数取模，使用c(n,k)=c(n-1,k-1)+c(n,k-1)来求。最后需要注意的是，由于取模的影响，容斥原理算出来的值可能为负，若为负，则加1000000007； 
#include<iostream>
#define MOD 1000000007
using namespace std;
int main(){
    int s,a,b,c;
    long long t[50];
    long long C[51][51];
    for(int i=0;i<=50;i++){
        C[i][0]=1;
    }
    for(int i=1;i<=50;i++){
        for(int j=0;j<=50;j++){
            if(i>j){C[j][i]=0;}
            else{
                C[j][i]=(C[j-1][i-1]+C[j-1][i])%MOD;
            }
        }
    }
    while(cin>>s>>a>>b>>c){
        long long num=0;
        int m=max(a,max(b,c));
        for(int i=0;i<=s-m;i++){
            t[i]=C[s-i][a]*C[s-i][b]%MOD*C[s-i][c]%MOD*C[s][i]%MOD;
        }
        for(int i=0;i<=s-m;i++){
            if(i%2==0){
                num=(num+t[i])%MOD;
            }
            else{
                num=(num-t[i])%MOD;
            }
        }        
        long long p=num%MOD;
        if(p<0){p+=MOD;}
        cout<<p<<endl;
    }
}

发表于 2020-08-26 18:46:43 回复(0)
一只鱼笔头像 一只鱼笔
显然是dp啊，dp[i][j][k][l]表示目前已经分配了i个任务，给a分配了j个任务，b分配了k个任务，c分配了l个任务的方案数，转移的时候至少要给其中一个人分配任务。知道状态看代码应该就比较好懂了吧
其实实际的时候可以用滚动数组优化掉一维
复杂度O(n^4) 
#include<bits/stdc++.h>
using namespace std;
const int N=55;
const int mod=1e9+7;
int dp[N][N][N][N];
void dfs(int i,int j,int k,int l){
    for(int a=1;a<8;a++){
        int jj=((a&4)!=0);
        int kk=((a&2)!=0);
        int ll=((a&1)!=0);
       // cout<<jj<<kk<<ll<<endl;
        dp[i+1][j+jj][k+kk][l+ll]+=dp[i][j][k][l];
        dp[i+1][j+jj][k+kk][l+ll]%=mod;
    }
}
int main(){
    int s,a,b,c;
    cin>>s>>a>>b>>c;
    dp[0][0][0][0]=1;
    for(int i=0;i<=s;i++){
        for(int j=0;j<=a&&j<=i;j++){
            for(int k=0;k<=b&&k<=i;k++){
                for(int l=0;l<=c&&l<=i;l++){
                    dfs(i,j,k,l);
                }
            }
        }
    }
    printf("%d\n",dp[s][a][b][c]);
    return 0;
}


编辑于 2019-08-17 08:45:30 回复(0)
羚羊在找内推头像 羚羊在找内推 
我的代码好丑哦...


 #include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007 

ll n, m, p;
/**
 * 
 * @author zyh
 * 
 * @version 1.0
 * 
 * 说明:快速次幂
 */
ll pow_m(ll a, ll k, ll p)
{     ll ans = 1;     ll tmp = a%p;     while (k)     {         if (k & 1)ans = ans*tmp%p;         tmp = tmp*tmp%p;         k >>= 1;     }     return ans;
}
/**
 * 
 * @author zyh
 * 
 * @version 1.0
 * 
 * 说明:求C(n,m)对p取摸之后的结果
 */
ll C(ll n, ll m, ll p)
{     if (m>n)return 0;     ll a = 1, b = 1;     for (int i = 1;i <= m;i++)     {         a = a*(n + i - m) % p;         b = b*i%p;     }     return a*pow_m(b, p - 2, p) % p;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int s;
    vector<int>nums(3, 0);
    cin >> s ;
    for(int i = 0; i < 3; i++)
    {
        cin >> nums[i];
    }
    sort(nums.begin(),nums.end());
    int a = nums[2];
    int b = nums[1];
    int c = nums[0];
    
    long long int num1 = C(s, a, mod);
    long long ret = 0;
    // b在a未选的部分至少需要选几个任务
    int i = s - a - c > 0 ? s - a -c: 0;
    for(; i<= b && i <= s -a; i++)
    {
        ll num2 = (((C(s- a, i, mod) * C(a, b - i, mod)) % mod) * (C(a + i, c - (s -a -i), mod)) ) % mod;
        //cout << num1 << "  " << num2 << endl;
        ret = (ret + ((num2 * num1)%mod))%mod;
        //cout << ret <<endl;
    }
   
   cout << ret << endl;
    return 0;
}

发表于 2019-07-03 21:30:30 回复(0)
提交观点

问题信息

网易 2018 基础数学 数学 Java工程师
上传者：小小
难度：
7条回答 4242浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号