题目地址
1 #include <bits/stdc++.h>
2 typedef long long ll;
3 using namespace std;
4 const int MAX=1e5+5;
5 const int INF=1e9;
6 int s,m,n;
7 int cost[125];
8 //char sta[MAX];
9 string sta;
10 int able[125];
11 int dp[125][1<<8][1<<8];
12 int d_p(int i,int s0,int s1,int s2)
13 {
14 if(i==m+n)
15 return s2==(1<<s)-1?0:INF;
16 int& ans=dp[i][s1][s2];
17 if(ans>=0)
18 return ans;
19 ans=INF;
20 if(i>=m)//为应聘者
21 ans=d_p(i+1,s0,s1,s2);//不选
22 int m0=able[i]&s0,m1=able[i]&s1;
23 s0^=m0;s1=(s1^m1)|m0;s2|=m1;
24 ans=min(ans,cost[i]+d_p(i+1,s0,s1,s2));
25 return ans;
26 }
27 int main()
28 {
29 while(~scanf("%d%d%d",&s,&m,&n))
30 {
31 if(s==0)
32 break;
33 getchar();
34 memset(dp,-1,sizeof(dp));
35 memset(able,0,sizeof(able));
36 for(int i=0;i<m+n;i++)
37 {
38 getline(cin,sta);
39 int num=0,len=sta.length(),j;
40 for(j=0;j<len&&sta[j]>='0'&&sta[j]<='9';j++)
41 {
42 num=num*10+sta[j]-'0';
43 }
44 cost[i]=num;
45 num=0;
46 for(;j<len;j++)
47 {
48 if(sta[j]>='0'&&sta[j]<='9')
49 num=num*10+sta[j]-'0';
50 else
51 {
52 if(num)
53 {
54 --num;
55 able[i]|=(1<<num);
56 }
57 num=0;
58 }
59 }
60 if(num)
61 {
62 --num;
63 able[i]|=(1<<num);
64 }
65 }
66 printf("%d
",d_p(0,(1<<s)-1,0,0));
67 }
68 return 0;
69 }