（状压dp）uva 10817 Headmaster's Headache

题目地址

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAX=1e5+5;
const int INF=1e9;
int s,m,n;
int cost[125];
//char sta[MAX];
string sta;
int able[125];
int dp[125][1<<8][1<<8];
int d_p(int i,int s0,int s1,int s2)
{
    if(i==m+n)
        return s2==(1<<s)-1?0:INF;
    int& ans=dp[i][s1][s2];
    if(ans>=0)
        return ans;
    ans=INF;
    if(i>=m)//为应聘者
        ans=d_p(i+1,s0,s1,s2);//不选
    int m0=able[i]&s0,m1=able[i]&s1;
    s0^=m0;s1=(s1^m1)|m0;s2|=m1;
    ans=min(ans,cost[i]+d_p(i+1,s0,s1,s2));
    return ans;
}
int main()
{
    while(~scanf("%d%d%d",&s,&m,&n))
    {
        if(s==0)
            break;
        getchar();
        memset(dp,-1,sizeof(dp));
        memset(able,0,sizeof(able));
        for(int i=0;i<m+n;i++)
        {
            getline(cin,sta);
            int num=0,len=sta.length(),j;
            for(j=0;j<len&&sta[j]>='0'&&sta[j]<='9';j++)
            {
                num=num*10+sta[j]-'0';
            }
            cost[i]=num;
            num=0;
            for(;j<len;j++)
            {
                if(sta[j]>='0'&&sta[j]<='9')
                    num=num*10+sta[j]-'0';
                else
                {
                    if(num)
                    {
                        --num;
                        able[i]|=(1<<num);
                    }
                    num=0;
                }
            }
            if(num)
            {
                --num;
                able[i]|=(1<<num);
            }
        }
        printf("%d\n",d_p(0,(1<<s)-1,0,0));
    }
    return 0;
}