hdu 6006 Engineer Assignment 状压dp

Engineer Assignment

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

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

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

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

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

题意：给你一些N个地点，每个地点有多个种类问题，M个工程师，一个工程可以解决一些问题；求最多解决几个；

思路：状态压缩dp；

　　　dp[i][j]表示解决前i个，用状态压缩的使用了j的工程师，最多解决问题数；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<bitset>
#include<time.h>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=10+10,M=1e6+10,inf=1e9+7,MOD=1e9+7;
const LL INF=1e18+10,mod=1e9+7;

struct Hash
{
    int flag[110],tot;
    void init()
    {
        memset(flag,0,sizeof(flag));
        tot=0;
    }
    int operator [](int x)
    {
        if(flag[x])return flag[x];
        flag[x]=++tot;
        return flag[x];
    }
}f;
LL a[N],b[N];
int dp[N][3000];
int check(int pos,int x,int y,int m)
{
    LL ans=0;
    for(int i=1;i<=m;i++)
    {
        LL xx=(1LL<<(i-1))&x;
        LL zz=(1LL<<(i-1))&y;
        if(xx^zz)
        {
            ans|=b[i];
        }
    }
    if((ans|a[pos])==ans)return 1;
    return 0;
}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        f.init();
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            int t;
            scanf("%d",&t);
            while(t--)
            {
                int x;
                scanf("%d",&x);
                a[i]|=(1LL<<(f[x]-1));
            }
        }
        for(int i=1;i<=m;i++)
        {
            int t;
            scanf("%d",&t);
            while(t--)
            {
                int x;
                scanf("%d",&x);
                b[i]|=(1LL<<(f[x]-1));
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=(1<<m)-1;j++)
            {
                for(int k=0;k<=j;k++)
                {
                    if((k|j)!=j)continue;
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+check(i,j,k,m));
                }
            }
        }
        printf("Case #%d: %d
",cas++,dp[n][(1<<m)-1]);
    }
    return 0;
}