[UVA11825]Hackers' Crackdown(状压dp)

题目传送门洛谷

果然水题做多了连半道难点的都能给咱干蒙...

水题做多了降智 --鲁迅

题目大意:见传送门

心路历程见末尾

正解(大概):

状压

虽然有些难以理解，但是这道题里面有两种集合

一种是第i台电脑所联通的合起来就是S[i](代码内的line[i])

另一种是指已经用了哪几台电脑

思路开始

反正无论如何一定得用几个S[i]拼成一个全集(1<<n)-1

于是就有了

 1 struct Union
 2 {
 3     int A;
 4 }U[1<<16];//可以凑出来一个全集的几个电脑的集合
 5 int Uarr;
 6 void getU(int st,int A,int p)
 7 {
 8     if(st==((1<<n)-1))//这几个电脑的line集合拼成了全集
 9     {
10         U[Uarr].A=A;
11         Uarr++;
12         return;
13     }
14     if(p>=n) return;
15     getU(st|line[p],A|(1<<p),p+1);//集合里加这个电脑
16     getU(st,A,p+1);//不加
17 }

好孩子不要急着就看哦(大雾)

(写法比较朴素的说)

好了我们的重点部分已经完事了

(啥你这就完事了?)

确实想到这个就好写了...

如果你做过[NOIP2016]愤怒的小鸟

那这题就更好想到了

好了上代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using std::sort;
 5 int max(int a,int b){return a>b?a:b;}
 6 int n,m;
 7 
 8 int dp[1<<16];
 9 int line[16];
10 
11 struct sta
12 {
13     int s,sc;
14 }s[1<<16];
15 int sarr;
16 void getsta(int st,int sc,int p)
17 {
18     if(p>=n)
19     {
20         s[sarr].s=st;
21         s[sarr].sc=sc;
22         sarr++;
23         return;
24     }
25     getsta(st|(1<<p),sc+1,p+1);
26     getsta(st,sc,p+1);
27 }
28 
29 struct Union
30 {
31     int A;
32 }U[1<<16];
33 int Uarr;
34 void getU(int st,int A,int p)
35 {
36     if(st==((1<<n)-1))
37     {
38         U[Uarr].A=A;
39         Uarr++;
40         return;
41     }
42     if(p>=n) return;
43     getU(st|line[p],A|(1<<p),p+1);
44     getU(st,A,p+1);
45 }
46 
47 bool cmp(sta a,sta b)//状态按照1的数量排序(咱就好这一手) 
48 {
49     if(a.sc==b.sc) return a.s<b.s;
50     else return a.sc<b.sc;
51 }
52 
53 void memclr()
54 {
55     memset(line,0,sizeof(line));
56     memset(dp,0,sizeof(dp));
57     Uarr=0;
58     sarr=0;
59 }
60 int main()
61 {
62 int xin,kk=0;
63 while(scanf("%d",&n)!=EOF)
64 {
65     if(n==0) return 0;
66     memclr();
67     getsta(0,0,0);
68     sort(s,s+sarr,cmp);
69     for(int i=0;i<n;i++)
70     {
71         scanf("%d",&m);
72         line[i]|=(1<<i);
73         for(int j=1;j<=m;j++)
74         {
75             scanf("%d",&xin);
76             line[i]|=(1<<xin);
77         }
78     }
79     getU(0,0,0);
80     for(int si=0;si<sarr;si++)
81     {
82         for(int Ui=0;Ui<Uarr;Ui++)
83         {
84             if((s[si].s&U[Ui].A)==U[Ui].A)
85             {
86                 dp[s[si].s]=max(dp[s[si].s],dp[s[si].s^U[Ui].A]+1);
87             }
88         }
89     }
90     printf("Case %d: %d
",++kk,dp[(1<<n)-1]);
91 }
92     return 0;
93 }

好孩子要自己思考~

看上去做的十分轻松

实际上

心路历程如下:

一开始:emmmm外层电脑使用状态里面枚举下一个使用每个电脑然后dp里存v和状态...

写完:???

等下等下从下面能继承过来一堆状态啊啊啊

变成(2^n)^k了啊啊啊啊啊

心态爆炸

Ah~(油库里音)

切题后:

啥?子集的子集是3^n?

完了我菜死了

陷入沉思...

3^n*n似乎也会T死

这至少证明了我原先的思路似乎没啥可行性而不是半途而废(什么逻辑)

心态平衡了

Ah~(油库里音)

以上

本题完结

记住

水题做多了降智

我没说过这句话 --鲁迅