题目链接:http://fastvj.rainng.com/contest/307763#problem/D
题目大意:
思路:
思路比较容易明白,就是代码比较不容易写,对位运算必须非常熟悉。
#include<bits/stdc++.h>
using namespace std;
int st[150];
int fy[150];
int s, n, m;
int dp[150][(1<<8)+1][(1<<8)+1];
int dfs(int i, int s0, int s1, int s2)
{
if(i>m+n)
{
if(s2==(1<<s)-1)//如果满足条件
{
return 0;
}
else
{
return 10000000;
}
}
int& ans=dp[i][s1][s2];
if(ans!=-1)
{
return ans;
}
ans=(10000000);
if(i>m)//m+1-n+m才可以不选择
{
ans=dfs(i+1, s0, s1, s2);//不选择这个老师
}
int m0=s0&st[i];//之前没有的&现在教的科目=新增加的科目
int m1=s1&st[i];//之前一个人教&现在教的科目=新增加有两个人教的科目
s0^=m0;//现在没有人教的科目=之前没有人教的科目-新增加的科目
s1=(s1^m1)|m0;//现在一个人教的科目=之前一个教的科目-新增加有两个人教的科目
s2=(s2)|m1;//现在有两个人教的科目=之前有两个人交的科目+新增加有两个人教的科目
ans=min(ans, dfs(i+1, s0, s1, s2)+fy[i]);//选择这个老师
return ans;
}
int main()
{
while(scanf("%d%d%d",&s,&m,&n),n*m*s)
{
memset(st, 0, sizeof(st));
memset(dp, -1, sizeof(dp));
for(int i=1;i<=n+m;i++)
{
scanf("%d",&fy[i]);
char k;
while(scanf("%c",&k),k!='\n')
{
if(k>='0'&&k<='9')
{
st[i]=st[i]|(1<<(k-'1'));
}
}
}
cout<<dfs(1, (1<<s)-1, 0, 0)<<endl;
}
return 0;
}