UVA10817-----Headmaster's Headache-----状态压缩的背包（记忆化搜索实现）

本文出自：http://blog.csdn.net/dr5459

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1758

题目意思：

某校有n个教师和m个求职者。已知每人的工资和能交的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘

解题思路：

因为课程的个数S最多才8个，我们可以想到用二进制压缩

例：

科目个数最多为8，用16位2进制数来表示。2进制中从右往左数，前8为表示有1位老师教该门课程，后8为表示有2位老师教（该位-8）的课程，

当s=8时，00000010 00000001表示1个老师教第一门课，2个老师教第2门课。这样 11111111 00000000 即为所要求的目标状态，代码中用T表示。

令dp[i][j]表示在前 j 个求职工中达到状态 i的最小花费。用st表示当前状态，则

dp[i][j] = min{dp[i][j], dp[i][j+1], dp[i+第j个人能够教的科目][j+1] +第j个人的工资}

定义函数int DP(int st,int i)表示第ｉ个人开始到ｎ个人结束，从状态 st 开始到目标状态的最小花费。这里用到记忆化搜索。

感谢：http://www.tuicool.com/articles/qMna2e

代码：

#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#include<vector>#include<iostream>using namespace std;const int maxn = 110;const int maxs = 1<<16+1;int s,m,n;char stream[maxn];int dp[maxn][maxs];int value[maxn];bool vis[maxn][maxs];vector<int> lession[maxn];int ALL;int DP(int now,int x){    if(vis[x][now])        return dp[x][now];    vis[x][now] = 1;    if(now == ALL)        return dp[x][now]=0;    if(x==n)        return 0x3f3f3f3f;    int next = now;    int len = lession[x].size();    //cout<<"x "<<x<<endl;    for(int i=0;i<len;i++)    {        int tmp = lession[x][i];        //cout<<x<<" "<<i<<" "<<tmp<<endl;        if((1<<(s+tmp)) & next)            continue;        if((1<<(tmp)) & next)            next = next-(1<<tmp)+(1<<(s+tmp));        else            next = next+(1<<tmp);    }    if(next != now)        dp[x][now] = min(dp[x][now],DP(next,x+1)+value[x]);    dp[x][now] = min(dp[x][now],DP(now,x+1));    return dp[x][now];}int main(){    while(~scanf("%d%d%d",&s,&m,&n) && s+m+n)    {        int sum = 0;        int status = 0;        memset(vis,false,sizeof(vis));        memset(dp,0x3f3f3f3f,sizeof(dp));        int tmp;        for(int i=0;i<m;i++)        {            scanf("%d",&tmp);            sum+=tmp;            gets(stream);            int len = strlen(stream);            for(int j=0;j<len;j++)            {                sscanf(stream+j,"%d",&tmp);                tmp--;//便于2进制                //cout<<"tmp "<<tmp<<endl;                while(isdigit(stream[j]))                    j++;                j++;                if((1<<(s+tmp)) & status)                    continue;                if((1<<(tmp)) & status)                {                    status = status - (1<<(tmp)) + (1<<(s+tmp));                }                else                    status = status + (1<<(tmp));            }        }        for(int i=0;i<n;i++)            lession[i].clear();        for(int i=0;i<n;i++)        {            scanf("%d",&value[i]);            gets(stream);            int len = strlen(stream);            for(int j=0;j<len;j++)            {                sscanf(stream+j,"%d",&tmp);                tmp--;                lession[i].push_back(tmp);                while(isdigit(stream[j]))                    j++;                j++;            }        }        ALL = 0;        for(int i=s;i<2*s;i++)        {            ALL += (1<<i);        }        //cout<<ALL<<" "<<status<<endl;        printf("%d\n",sum+DP(status,0));    }    return 0;}