uva 10817 Headmaster's Headache 出发dp 位计算

出发dp，用在一些议题的操作非常~

给出s个课程。m个教师。n个求职者，教师必须招聘。然后招聘一些求职者，使得每一门课都至少有两个老师能教。问题就转换成了招聘哪些求职者使得花费最少。由于s范围小于8。则能够用二进制表示，用集合s1表示恰好有一个人教的课的集合，用集合s2表示有两个人教的课的集合，则每次状态转移即为选择这名求职者还是不选（教师必须选）详细看代码。

d(i,s1,s2) = min{ d(i+1,s1',s2')+c[i],d(i+1,s1,s2)} 第一项表示聘用，第二项表示不聘用。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define mem(name,value) memset(name,value,sizeof(name))

#define FOR(i,n) for(int i=1;i<=n;i++)

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=130;

const int maxs=8;

int n,m,s,d[maxn][1<<maxs][1<<maxs],st[maxn],c[maxn];//st表示第i个人能够教的课程的集合。c表示花费

void init(){

    mem(d,-1); mem(st,0); mem(c,0);

    for(int i=0;i<m+n;i++){

        scanf("%d",c+i);

        while(1){

            int t; char c1;

            scanf("%d",&t);

            st[i] |= (1<<(t-1));

            c1 = getchar();

            if(c1=='\n') break;

        }

    }

}

int dp(int i,int s0,int s1,int s2){ //s0 表示恰好一个人都没有教的课的集合。也能够用s1和s2算出来。

    if(i==m+n) return s2==(1<<s)-1?0:inf;

    //假设已经考虑到第m+n个人了，编号是1~m+n-1，则人已经选完。若s2集合中没有全部课。则不符合题意。

    int& ans = d[i][s1][s2];

    if(ans!=-1) return ans;

    ans = inf;

    if(i>=m) ans = dp(i+1,s0,s1,s2);    //仅仅有当选择求职者的时候才用考虑是否聘用。

int m0 = st[i]&s0, m1 = st[i]&s1;   //m0表示在一个人都没有教的课中，第i个人能够教哪些，m1同理。

s0=s0^m0;  s1=(s1^m1)|m0; s2=s2|m1; //将s0中有人教的课去掉。算到s1上。s2同理

    ans = min(ans,c[i]+dp(i+1,s0,s1,s2)); //和不聘用的价格比較

    return ans;

}

int main(){

   // freopen("in.txt","r",stdin);

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

        init();

        int ans = dp(0,(1<<s)-1,0,0);   //答案为还没考虑不论什么一个人，和没有不论什么一门课有人教

        printf("%d\n",ans);

    }

    return 0;

}

秒客网

uva 10817 Headmaster's Headache 出发dp 位计算

相关文章