题目大意：有一些老师，每一位都有自己的工资以及教授的课程。共s<=8个课程。其中的一些老师必须选择，问你保证每节课至少有一个老师的最少总工资。

题解：

首先很容易想到状态压缩，搞一个3进制的数，分别表示每一门课程的情况，一共3⁸=6561。但是这样是不行的，相当于暴力啊！
一个套路：三进制转化为二进制*2。也就是搞一个2¹⁶的数，1~8和9~16表示每门课程，这样就可以利用位运算了。
然后知道这个就很显然的，一个背包问题。要注意，这样转化为二进制之后，要定义一条规则，每次添加课程，优先1~8位，有了就再加到9~16位即可。
处理出所有强制选择的老师的授课状态S，令dp[S]=sum{c[]}。其他的全是INF。然后从All=(1<<(s*2)-1到S。当成01背包做即可。

 #include<queue>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register

 #define LL long long

 #define fre(a) freopen(a".in","r",stdin);//freopen(a".out","w",stdout);

 using namespace std;

 const int MAXN=;

 int s,n,m,S,sum,All;

 int c[MAXN],a[MAXN],dp[<<];

 char ch;

 int main()

 {

    while(scanf("%d%d%d",&s,&n,&m)!=EOF)

       {

          if(s==)break;

          All=(<<(s*))-;

          for(int i=,flag,x;i<=n+m;i++)//鬼里鬼气的输入

             {

                a[i]=;

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

                flag=;

                while()

                   {

                      ch=getchar();

                      while(ch<''||ch>'')

                         {

                            if(ch=='\n'||ch=='\r') { flag=; break; }

                            ch=getchar();

                         }

                      if(flag)break;

                      x=;

                      while(''<=ch&&ch<='')x=x*+(ch-''),ch=getchar();

                      a[i]|=(<<(x-));

                      if(ch=='\n'||ch=='\r')break;

                   }

             }

          S=sum=;

          for(int i=;i<=n;i++)//按照规则，优先填后面的

             {

                sum+=c[i];

                int p=S&a[i];

                S|=(p<<s);

                S|=a[i];

             }

          memset(dp,0x3f3f3f3f,sizeof dp);

          dp[S]=sum;

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

             {

                for(int j=All;j>=S;j--)//按照规则，优先填后面的

                   {

                      int p=a[i]&j;

                      p=a[i]|(p<<s);

                      dp[j|p]=min(dp[j|p],dp[j]+c[i]);

                   }

             }

          printf("%d\n",dp[All]);

       }

    return ;

 }

巴特西

UVA - 10817 Headmaster's Headache

题解：

最新文章

热门文章