UVa 10817 Headmaster’s Headache

题目

◇题目传送门◆（由于UVa较慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

某校有$M$个教师和$N$个求职者，需要讲授$S$个课程。已知每个人的工资$c$和能教的课程集合，要求支付最少的工资使得每门课程都有至少两个人教。教师不能辞退。

思路

这道题$s$非常小，可以考虑使用状压DP来解决。

定义状态$f[i][s_1][s_2]$为考虑前$i$个人的最小花费，且使得有一个人教的课程集合为$s_1$，有两个人教的课程集合为$s_2$。

将所有人从$1$一起编号，则编号为$1\ldots M$的人是教师，编号为$M+1\ldots N+M$的人是求职者。

当我们聘用一个人时，状态就可以转移到$f[i+1][s_1'][s_2']$，$s_1',s_2'$表示招聘第$i$个人后，$s_1,s_2$的新值，$s_1',s_2'$的计算方法见代码。

当我们不聘用一个人时，状态就可以转移到$f[i+1][s_1][s_2]$。注意只有当$i\ge M+1$时才可以不聘用。

总结一下状态转移方程：

$$f[i][s_1][s_2]=\begin{cases}f[i+1][s_1'][s_2']+c[i]&i<M+1\\\min\{f[i+1][s_1'][s_2']+c[i],f[i+1][s_1][s_2]\}&i\ge M+1\end{cases}$$

正解代码

代码采用记忆化搜索实现。并在递归时多使用了一个参数$s_0$，表示没有人能够教的课程集合。这个参数只是为了计算方便，并不需记忆（因为有了$s_2,s_1$就能推出$s_0$）。

注意代码中课程是从0开始标号。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxm=20;
const int Maxn=100;
const int Maxs=8;
const int INF=0x3f3f3f3f;int S,M,N,c[Maxm+Maxn+5],st[Maxm+Maxn+5];
int f[Maxm+Maxn+1][1<<Maxs+1][1<<Maxs+1];int DFS(int pos,int s0,int s1,int s2) {if(pos>M+N)return s2==(1<<S)-1?0:INF;//注意若有科目没有两个人教则返回INF//<<的优先级比==低!!!int &res=f[pos][s1][s2];if(res!=-1)return res;int ret=INF;if(pos>M)ret=DFS(pos+1,s0,s1,s2);//不招聘int m0=st[pos]&s0,m1=st[pos]&s1;//计算招聘一个人后教的人数增加的科目s0^=m0,s1=(s1^m1)|m0,s2|=m1;//计算新值ret=min(ret,DFS(pos+1,s0,s1,s2)+c[pos]);//招聘return res=ret;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d %d",&S,&M,&N)!=EOF&&S&&M&&N) {for(int i=1;i<=M+N;i++) {scanf("%d",&c[i]);int t=0;char ch;while(ch=getchar()) {if('0'<=ch&&ch<='9')t|=1<<(ch-'0'-1);else if(ch=='\n'||ch==EOF)break;}//读入时注意处理课程编号st[i]=t;}memset(f,-1,sizeof f);printf("%d\n",DFS(1,(1<<S)-1,0,0));}return 0;
}