【Link】:

【Description】



一个学校,有s门课程(1<=s <=8),里面本身已经有m个老师了,然后还想招聘n个老师；

给出这m个老师和n个来应聘的老师的信息;

(c[i]->工资,以及他们能教哪几门课程);

原本的m个老师一定要继续保留下来;

问你在这个条件下,如何选取这n个老师中的一些人;

使得每门课都至少有两个人能教,且花费的总工资最少.

【Solution】



设f[i][j]表示前i个老师(不包括原有的m个老师),能教课程的状态为j的情况下最少需要花多少工资;

这里j由16位二进制组成

其中第2x位,表示第x门课程有没有一个老师教,第2x+1位表示第x门课程有没有两个老师教.

然后枚举前i个老师,枚举当前状态j;

然后从f[i][j]转移到f[i+1][temp]和f[i+1][j]

这里temp是选了第i+1个老师后j变成的状态;

f[i+1][temp]=min(f[i+1][temp],f[i][j]+c[i+1])

f[i+1][j]=min(f[i+1][j],f[i][j])

最后输出f[n][22∗s−1]



【NumberOf WA】



0



【Reviw】



选好了状态就不难写啦.

读到行末用gets.



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 100;

const int NN = 65536;

const int INF = 0x3f3f3f3f;

int s,m,n,temp1,temp2,two[20];

int c[N+10],sta[N+10],f[N+10][NN+10];

char temp[40];

int main(){

    //Open();

    //Close();

    two[0] = 1;

    rep1(i,1,19)

        two[i] = two[i-1]*2;

    while (~scanf("%d%d%d",&s,&m,&n) && s){

        rep1(i,0,N)

            rep1(j,0,NN)

                f[i][j] = INF;

        rep1(i,1,N) sta[i] = 0;

        temp1 = 0,temp2 = 0;

        rep1(i,1,m){

            int x;

            scanf("%d",&x);

            temp2+=x;

            gets(temp);

            int len = strlen(temp);

            rep1(j,0,len-1)

                if (isdigit(temp[j])){

                    x = temp[j]-'0';

                    if (temp1 & two[2*(x-1)])

                        temp1 |= two[2*(x-1)+1];

                    else

                        temp1 |= two[2*(x-1)];

                }

        }

        f[0][temp1] = temp2;

        rep1(i,1,n){

            scanf("%d",&c[i]);

            gets(temp);

            int len = strlen(temp);

            rep1(j,0,len-1)

                if (isdigit(temp[j])){

                    int x;

                    x = temp[j]-'0';

                    sta[i] |= two[2*(x-1)];

                }

        }

        rep1(i,0,n-1)

            rep1(j,0,two[2*s]-1)

                if (f[i][j]<INF){

                    int temp3 = j;

                    rep1(k,0,s-1){

                        if (two[2*k]&sta[i+1]){

                            if (j&two[2*k])

                                temp3 |= two[2*k+1];

                            else

                                temp3 |= two[2*k];

                        }

                    }

                    f[i+1][j] = min(f[i+1][j],f[i][j]);

                    f[i+1][temp3] = min(f[i+1][temp3],f[i][j] + c[i+1]);

                }

        printf("%d\n",f[n][two[2*s]-1]);

    }

    return 0;

}