題意：

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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。