题意:
某校有m个教师和n个求职者,已知每个人的工资和可以教的课程,现在要求每门课程至少有两个教师教学;求工资和最少是多少;
思路:
由于课程数较少,可以用dp[k][i][j]表示在当前第k个求职者时i表示还需要一个教师的课程,j表示还需要2个教师的课程;
转移的时候可以这样:可以分成选择招聘或者不招聘;具体的看代码和注释;如果遇到的dp题目选择的数目太多,而合法的情况少,我们可以考虑用合法的情况构造转移方程;
AC代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <bits/stdc++.h> #include <stack> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++) #define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar()); for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar()); F && (num=-num); } int stk[70], tp; template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar(' '); } const LL mod=20071027; const double PI=acos(-1.0); const int inf=1e9; const int N=(1<<8)+100; const int maxn=(1<<8); const double eps=1e-8; int a[N]; int dp[102][N][N],flag[10],cost[110],po[110],fa[10]; char str[200]; int main() { while(1) { int s,m,n,sum=0; read(s);read(m);read(n); if(!s)break; mst(flag,0); For(i,1,m) { gets(str); int cnt=0,len=strlen(str); int temp=0,num=0; while(cnt<len) { if(str[cnt]==' ') { a[++num]=temp; temp=0; } else temp=10*temp+str[cnt]-'0'; cnt++; } a[++num]=temp; sum+=a[1]; mst(fa,0); For(j,2,num)fa[a[j]-1]++; For(j,0,s-1)if(fa[j])flag[j]++; } For(i,1,n) { gets(str); int cnt=0,len=strlen(str); int temp=0,num=0; while(cnt<len) { if(str[cnt]==' ') { a[++num]=temp; temp=0; } else temp=10*temp+str[cnt]-'0'; cnt++; } a[++num]=temp; cost[i]=a[1]; mst(fa,0); For(j,2,num)fa[a[j]-1]++; po[i]=0; For(j,0,s-1)if(fa[j])po[i]=po[i]+(1<<j); } For(k,0,n)For(i,0,maxn)For(j,0,maxn)dp[k][i][j]=inf; int temp1=0,temp2=0; For(i,0,s-1) { if(flag[i]>=2)continue; else if(flag[i]==1)temp1=temp1+(1<<i); else temp2=temp2+(1<<i); } dp[0][temp1][temp2]=sum; For(i,1,n) { for(int j=maxn-1;j>=0;j--) { for(int k=0;k<maxn;k++) { if(j&k)continue; int l=j-(j&po[i]),r=k-(k&po[i]); //j中表示还缺一个教师,加上这个老师,那么这门课就变成了需要0个老师了; //r=k-k&po[i]也是一个道理,不过是缺两个变成了缺一个了 dp[i][l+(k&po[i])][r]=min(dp[i][l+(k&po[i])][r],dp[i-1][j][k]+cost[i]); dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]); } } } int ans=inf; for(int i=0;i<=n;i++)ans=min(ans,dp[i][0][0]); cout<<ans<<endl; } return 0; }