Headmaster's Headache UVA - 10817

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

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:面向对象——对继承、关联、聚合、组合、依赖的理解

下一篇:NOIp模拟1 Permutation