uva 10817 Headmaster's Headache 出发dp 位计算

#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;}