首页 > > 程序设计 > C/C++ >

Headmaster's Headache UVA - 10817

2018-06-17 22:05:20来源：未知阅读 ()

UVA-10817

ans[i][s1][s2]表示考虑前i个人时，有至少1人教的科目集合为s1，有至少2人教的科目集合为s2时的最少工资
集合用一个数字表示，转换成二进制后从后面开始数第i位的状态(1/0)表示第i个科目的状态(满足/不满足某条件)
st[i]表示第i个人能教的课程集合,cost[i]表示第i个人的工资
ans[i][s1'][s2']=min(ans[i-1][s1'][s2'],ans[i-1][s1][s2]+cost[i])
s1'=s1|st[i]
s2'=s2|(s1&st[i])
压缩掉一维：
显然，s1'>=s1,s2'>=s2
因此,ans[s1'][s2']=min(ans[s1'][s2'],ans[s1][s2]+cost[i]) s1和s2从大到小

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 char tt[500];
 6 int s,m,n,ans1,sa,sb;
 7 int ans[1<<8][1<<8];
 8 int st[110],cost[110];
 9 int main()
10 {
11     int i,t,point,maxj,j,j1;
12     scanf("%d%d%d",&s,&m,&n);
13     while(s!=0)
14     {
15         memset(ans,0x3f,sizeof(ans));
16         memset(st,0,sizeof(st));
17         cin.getline(tt,500);
18         ans1=0;
19         sa=0;sb=0;
20         for(i=1;i<=m;i++)
21         {
22             //memset(tt,'\0',sizeof(tt));
23             cin.getline(tt,500);
24             point=0;
25             sscanf(tt,"%d",&t);
26             ans1+=t;
27             while(tt[point]<='9'&&tt[point]>='0')    ++point;
28             while(tt[point]==' ')    ++point;
29             while(point<strlen(tt))
30             {
31                 sscanf(tt+point,"%d",&t);
32                 t=1<<(t-1);
33                 sb|=sa&t;
34                 sa|=t;
35                 while(tt[point]<='9'&&tt[point]>='0')    ++point;
36                 while(tt[point]==' ')    ++point;
37             }
38         }
39         ans[sa][sb]=ans1;
40         for(i=1;i<=n;i++)
41         {
42             //memset(tt,'\0',sizeof(tt));
43             cin.getline(tt,500);
44             point=0;
45             sscanf(tt,"%d",&cost[i]);
46             while(tt[point]<='9'&&tt[point]>='0')    ++point;
47             while(tt[point]==' ')    ++point;
48             while(point<strlen(tt))
49             {
50                 sscanf(tt+point,"%d",&t);
51                 st[i]|=1<<(t-1);
52                 while(tt[point]<='9'&&tt[point]>='0')    ++point;
53                 while(tt[point]==' ')    ++point;
54             }
55         }
56         maxj=(1<<s)-1;
57         for(i=1;i<=n;i++)
58             for(j=maxj;j>=0;j--)
59                 for(j1=maxj;j1>=0;j1--)
60                 {
61                     sa=j|st[i];
62                     sb=j1|(j&st[i]);
63                     ans[sa][sb]=min(ans[sa][sb],ans[j][j1]+cost[i]);
64                 }
65         printf("%d\n",ans[maxj][maxj]);
66         scanf("%d%d%d",&s,&m,&n);
67     }
68     return 0;
69 }