HDU6006-Engineer Assignment
程序员文章站
2022-05-22 10:16:20
...
Engineer Assignment
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 131 Accepted Submission(s): 40
Problem Description
In Google, there are many experts of different areas. For example, MapReduce experts, Bigtable experts, SQL experts, etc. Directors need to properly assign experts to various projects in order to make the projects going smoothly.
There are N projects owned by a director. For the ith project, it needs Ci different areas of experts, ai,0,ai,1,⋅⋅⋅,ai,Ci−1 respective. There are M engineers reporting to the director. For the ith engineer, he is an expert of Di different areas, bi,0,bi,1,...,bi,Di−1.
Each engineer can only be assigned to one project and the director can assign several engineers to a project. A project can only be finished successfully if the engineers expert areas covers the project areas, which means, for each necessary area of the project, there is at least one engineer
masters it.
The director wants to know how many projects can be successfully finished.
There are N projects owned by a director. For the ith project, it needs Ci different areas of experts, ai,0,ai,1,⋅⋅⋅,ai,Ci−1 respective. There are M engineers reporting to the director. For the ith engineer, he is an expert of Di different areas, bi,0,bi,1,...,bi,Di−1.
Each engineer can only be assigned to one project and the director can assign several engineers to a project. A project can only be finished successfully if the engineers expert areas covers the project areas, which means, for each necessary area of the project, there is at least one engineer
masters it.
The director wants to know how many projects can be successfully finished.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consisting of 2 integers, N the number of projects and M the number of engineers. Then N lines follow. The ith line
containing the information of the ith project
starts
with an integer Ci then Ci integers follow, ai,0,ai,1,...,ai,Ci−1 representing the expert areas needed for the ith project. Then another M lines follow. The ith line containing the information of the ith engineer starts with an integer Di then Di integers follow, bi,0,bi,1,...,bi,Di−1 representing the expert areas mastered by ithengineer.
with an integer Ci then Ci integers follow, ai,0,ai,1,...,ai,Ci−1 representing the expert areas needed for the ith project. Then another M lines follow. The ith line containing the information of the ith engineer starts with an integer Di then Di integers follow, bi,0,bi,1,...,bi,Di−1 representing the expert areas mastered by ithengineer.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum number of projects can be successfully finished.
∙1≤T≤100.
∙1≤N,M≤10.
∙1≤Ci≤3.
∙1≤Di≤2.
∙1≤ai,j,bi,j≤100.
limits
∙1≤T≤100.
∙1≤N,M≤10.
∙1≤Ci≤3.
∙1≤Di≤2.
∙1≤ai,j,bi,j≤100.
Sample Input
1
3 4
3 40 77 64
3 10 40 20
3 40 20 77
2 40 77
2 77 64
2 40 10
2 20 77
Sample Output
Case #1: 2
Hint
For the first test case, there are 3 projects and 4 engineers. One of the optimal solution is to assign the first(40 77) and second engineer(77 64) to project 1, which could cover the necessary areas 40, 77, 64. Assign the third(40 10) and forth(20 77) engineer to project 2, which could cover the necessary areas 10, 40, 20. There are other solutions, but none of them can finish all 3 projects.
So the answer is 2.
Source
Recommend
jiangzijing2015
题意:一共有n个任务,完成某个任务需要会一些领域的人,一共有m个工程师,每个工程师会一些领域,问这些工程师最多完成多少任务
解题思路:先预处理出能第i个任务可以由哪些人一起完成,因为人数不多,所以可以用状态压缩,然后dp[i][j]来表示表前i个任务,状态为j时,最多完成的任务数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>
#include <set>
#include <vector>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
vector<int> x[20];
int a[20][10], b[20][10],vis[120];
int dp[20][1 << 11];
int main()
{
int t, n, m,cas=0;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) x[i].clear();
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i][0]);
for (int j = 1; j <= a[i][0]; j++)
scanf("%d", &a[i][j]);
}
for (int i = 0; i<m; i++)
{
scanf("%d", &b[i][0]);
for (int j = 1; j <= b[i][0]; j++)
scanf("%d", &b[i][j]);
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j<(1 << m); j++)
{
int cnt = 0;
memset(vis, 0, sizeof vis);
for (int k = 0; k<m; k++)
{
if (j&(1 << k))
{
cnt++;
for (int p = 1; p <= b[k][0]; p++)
vis[b[k][p]] = 1;
}
}
if (cnt>3) continue;
int flag = 1;
for (int k = 1; k <= a[i][0]; k++)
if (!vis[a[i][k]]) flag = 0;
if (flag) x[i].push_back(j);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j<(1 << m); j++)
{
int Size = x[i].size();
for (int k = 0; k<Size; k++)
if ((j | x[i][k]) == j) dp[i][j] = max(dp[i - 1][j - x[i][k]] + 1, dp[i][j]);
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
printf("Case #%d: %d\n", ++cas, dp[n][(1 << m) - 1]);
}
return 0;
}
上一篇: 二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)
下一篇: 【ACM入门】入门问题
推荐阅读
-
ES6基础之解构赋值(destructuring assignment)
-
C++代写,代写C++,C++程序代写,C++ assignment代写
-
Laravel中批量赋值Mass-Assignment的真正含义详解
-
Coursera | Applied Plotting, Charting & Data Representation in Python(UMich)| Assignment2
-
Error:ivalue require as left operant of assignment
-
Python | local variable 'xxxx' referenced before assignment
-
大量赋值(Mass assignment)
-
[Python]链式赋值(Chained assignment)
-
ES6--解构赋值(destructuring assignment)
-
逻辑赋值(Logical Assignment)