hdu 6006 Engineer Assignment（状压dp）

Engineer Assignment

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1170    Accepted Submission(s): 401

 

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.

 

 

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 ith engineer.

 

 

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.

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

2016 CCPC-Final

 

 

Recommend

jiangzijing2015   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 

这道题一看数据范围，就应该第一时间想到状压。

然后就在想状态转移。用dp【i】【j】代表前i个任务，当前工程师状态（用或不用）为就j，所能完成的最大任务数量。

还要预先处理一下当前状态为j时的所能完成哪些任务。

状态转移方程：

不完成当前任务i:  dp[i][j]=max(dp[i-1][j],dp[i][j])

完成当前任务i:   dp【i】【j   |  jjjj】=max(dp[i][ j  |  jjjj ],dp[i-1][jjjj]+1);////其中jjjj代表和j无交集的工程师状态。

后来大佬告诉我，这个是水状压。。。。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1<<11;
const int maxm=200;
int jud[maxn][maxm];///这个数组用来判断当前（engineer）状态i,能否完成j项目
int ok[maxm];
int c[maxm],a[maxn];
int cc[maxm][maxm];
int aa[maxm][maxm];
int dp[maxm][maxn];
int n,m;
void init(){
    memset(jud,0,sizeof(jud));
    for(int i=0;i<(1<<m);i++){
        memset(ok,0,sizeof(ok));
        for(int k=1;k<=m;k++){
            if((1<<(k-1))&i){///说明i这种排列，有k这个人
                for(int j=1;j<=c[k];j++){
                    ok[cc[k][j]]=1;///说明这门课是可以选的
                }
            }
        }
        int flag;
        for(int k=1;k<=n;k++){///
            flag=0;
            for(int j=1;j<=a[k];j++){
                if(!ok[aa[k][j]]){
                    flag=1;
                    break;
                }
            }
            if(flag==0)
                jud[i][k]=1;///就是状态i可以完成项目k
        }


    }
}
int main()
{
    int t;
    int cas=0;
    scanf("%d",&t);
    while(t--){
        cas++;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            for(int j=1;j<=a[i];j++){
                scanf("%d",&aa[i][j]);
               /// cout<<"111"<<endl;
            }
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&c[i]);
            for(int j=1;j<=c[i];j++){
                scanf("%d",&cc[i][j]);
              ///  cout<<"222"<<endl;
            }
        }
        init();
        int all=(1<<m);
        int ans=0;
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<all;j++){
                dp[i][j]=max(dp[i][j],dp[i-1][j]);///就是不选当前课
                 ans=max(ans,dp[i][j]);
                for(int k=0;k<all;k++){
                    if(!(k&j) && jud[k][i])///如果当前工程师和之前的没有重合，并且当前的这种状态可以完成工作i
                    {
                        dp[i][j|k]=max(dp[i][j|k],dp[i-1][j]+1);
                        ans=max(ans,dp[i][j|k]);
                    }
                }
            }
        }
       cout<<"Case #"<<cas<<": "<<ans<<endl;
    }
}