大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
出发dp，用在一些议题的操作非常~
给出s个课程。m个教师。n个求职者，教师必须招聘。然后招聘一些求职者，使得每一门课都至少有两个老师能教。问题就转换成了招聘哪些求职者使得花费最少。由于s范围小于8。则能够用二进制表示，用集合s1表示恰好有一个人教的课的集合，用集合s2表示有两个人教的课的集合，则每次状态转移即为选择这名求职者还是不选（教师必须选）详细看代码。
d(i,s1,s2) = min{ d(i+1,s1′,s2′)+c[i],d(i+1,s1,s2)} 第一项表示聘用，第二项表示不聘用。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define mem(name,value) memset(name,value,sizeof(name))
#define FOR(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=130;
const int maxs=8;
int n,m,s,d[maxn][1<<maxs][1<<maxs],st[maxn],c[maxn];//st表示第i个人能够教的课程的集合。c表示花费
void init(){
mem(d,-1); mem(st,0); mem(c,0);
for(int i=0;i<m+n;i++){
scanf("%d",c+i);
while(1){
int t; char c1;
scanf("%d",&t);
st[i] |= (1<<(t-1));
c1 = getchar();
if(c1=='\n') break;
}
}
}
int dp(int i,int s0,int s1,int s2){ //s0 表示恰好一个人都没有教的课的集合。也能够用s1和s2算出来。
if(i==m+n) return s2==(1<<s)-1?0:inf;
//假设已经考虑到第m+n个人了，编号是1~m+n-1，则人已经选完。若s2集合中没有全部课。则不符合题意。
int& ans = d[i][s1][s2];
if(ans!=-1) return ans;
ans = inf;
if(i>=m) ans = dp(i+1,s0,s1,s2); //仅仅有当选择求职者的时候才用考虑是否聘用。 int m0 = st[i]&s0, m1 = st[i]&s1; //m0表示在一个人都没有教的课中，第i个人能够教哪些，m1同理。
s0=s0^m0; s1=(s1^m1)|m0; s2=s2|m1; //将s0中有人教的课去掉。算到s1上。s2同理 ans = min(ans,c[i]+dp(i+1,s0,s1,s2)); //和不聘用的价格比較 return ans;}int main(){ // freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&s,&m,&n) && s && m &&n){ init(); int ans = dp(0,(1<<s)-1,0,0); //答案为还没考虑不论什么一个人，和没有不论什么一门课有人教 printf("%d\n",ans); } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117670.html原文链接：https://javaforall.net
