Headmaster's Headache

题意：

s门课程，现任老师有m个给出工资，和他们能教的课，现在有n个应聘的老师，给出费用和能教的课程标号，求使每门课都至少有两个老师教的最小花费

分析：

n个老师选或不选有背包的特征，n很小想到用状压，s1表示每门课至少有一个老师教的情况，s2表示每门课至少有2个老师教的情况

起始状态是现任老师形成，dp[(j|ca[i])][(ca[i]&j)|k]=min(dp[(j|ca[i])][(ca[i]&j)|k],dp[j][k]+cost[i]); ca[i]是i个应聘者能教课程的状态

#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <complex> #include <cassert> #include <utility> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> PII; typedef long long ll; #define lson l,m,rt<<1 #define pi acos(-1.0) #define rson m+1,r,rt<<11 #define All 1,N,1 #define read freopen("in.txt", "r", stdin) const ll INFll = 0x3f3f3f3f3f3f3f3fLL; const int INF= 0x3f3f3f3f; const int mod = 1000000007; int dp[1<<8][1<<8],s,m,n; int ca[200],cost[200],total; void solve(int s1,int s2){int ts=(1<<s)-1;memset(dp,0x3f,sizeof(dp));dp[s1][s2]=total;for(int i=m+1;i<=n+m;++i)for(int j=ts;j>=0;--j)for(int k=ts;k>=0;--k){if(dp[j][k]>=INF)continue;dp[(j|ca[i])][(ca[i]&j)|k]=min(dp[(j|ca[i])][(ca[i]&j)|k],dp[j][k]+cost[i]);}printf("%d\n",dp[ts][ts]); } int main() {char str[1000];int num[10];while(~scanf("%d%d%d",&s,&m,&n)){if(s==0&&m==0&&n==0)break;total=0;int s1=0,s2=0;memset(num,0,sizeof(num));for(int i=1;i<=n+m;++i){scanf("%d",&cost[i]);gets(str);ca[i]=0;for(int j=0;j<strlen(str);++j){if(isdigit(str[j])){int tmp=str[j]-'0';ca[i]|=(1<<(tmp-1));if(i<=m)num[tmp-1]++;}}if(i<=m){total+=cost[i];s1|=ca[i];}}for(int i=0;i<s;++i)if(num[i]>1)s2|=(1<<i);solve(s1,s2);} return 0; }

 

转载于:https://www.cnblogs.com/zsf123/p/4870281.html

总结

以上是生活随笔为你收集整理的Headmaster's Headache的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。