DAY 5 搜索

搜索

开篇：

mayan游戏（noip2011 day1 T3）

这道题就是个码量题，老师讲题时淡淡的说写完前两题就花一个半小时了，最后一题不快点打会调不出来，对于一个三个半小时就写两题的蒟蒻来说这。。。。这题就是老师口中的简单题。。。。

这种消数游戏应该每个人都玩过，顾名思义，要消数，所以就要打一个消数函数，消完数，他上面的数又不能在空中飘着（他又不是蜘蛛侠），所以还要打一个下移函数，由于这两天玩洛谷版的2048，得出一个结论，下面的被消掉后，上面的掉下来若能消还会继续消，直到不能消为止，所以还要一个判断有没有消完的函数，这题一看就知道要DFS，所以DFS怎么可以少。

但这题空间就128MB，时间也是巨卡，没有优化怎么能过？DFS这个东西十分神奇，因为他可以莫名其妙的剪枝（剪得你都不认识他了）

然后，你就可以打出这样的代码，一遍不过就重打吧。。。。。

剪枝：

相同颜色可以跳过，这很显然意见。
能往右边搜不要往左边搜，前一个往右边搜就等价于后一个往左边搜。
根据题目的优先度排序，当左边是空块时才考虑左移。
如果有一种颜色有X块，1<=X<=2，一定消不掉不合法

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 using namespace std;
  7 const int maxn=10;
  8 int mayan[maxn][maxn];
  9 int xxx;
 10 int ans[maxn][maxn];
 11 int n;
 12 inline int is_clear()
 13 {
 14     for(int i=0;i<5;i++)
 15     {
 16         for(int j=0;j<7;j++)
 17         {
 18             if(mayan[i][j])
 19             {
 20                 return 0;
 21             }
 22         }
 23     }
 24     return 1;
 25 }
 26 void new_ans(int i,int x,int y,int flag)
 27 {
 28     ans[i][1]=x;
 29     ans[i][2]=y;
 30     ans[i][3]=flag;
 31 }
 32 void fell_down(int x)
 33 {
 34     int tot=-1;
 35     for(int i=0;i<7;i++)
 36     {
 37         if(mayan[x][i])
 38         {
 39             mayan[x][++tot]=mayan[x][i];
 40         }
 41     }
 42     for(int i=tot+1;i<7;i++)
 43     {
 44         mayan[x][i]=0;
 45     }
 46     return ;
 47 }
 48 void clear() {
 49     bool flag = true;
 50     while(flag) {
 51         flag = false;
 52         int temp[10][10];
 53         memcpy(temp,mayan,sizeof(temp));
 54         for(int i=0;i<5;i++)
 55             for(int j=0;j<7;j++) 
 56             {
 57                 if(i >= 1 && i <= 3 && temp[i][j] && temp[i][j] == temp[i-1][j] && temp[i][j] == temp[i+1][j]) {
 58                     mayan[i][j] = 0;
 59                     mayan[i-1][j] = 0;
 60                     mayan[i+1][j] = 0;
 61                     flag = true;
 62                 }
 63                 if(j >= 1 && j <= 5 && temp[i][j] && temp[i][j] == temp[i][j-1] && temp[i][j] == temp[i][j+1]) {
 64                     mayan[i][j] = 0;
 65                     mayan[i][j-1] = 0;
 66                     mayan[i][j+1] = 0;
 67                     flag = true;
 68                 }
 69             }
 70                 
 71         if(!flag)
 72            return;
 73         for(int i=0;i<5;i++)
 74             fell_down(i);
 75     }
 76 }
 77 void dfs(int x)
 78 {
 79     if(is_clear()&&x==n)
 80     {
 81         for(int i=1;i<=x;i++)
 82         {
 83             cout<<ans[i][1]<<" "<<ans[i][2]<<" "<<ans[i][3]<<endl;
 84             xxx=1;
 85         }
 86         exit(0);
 87     }
 88     if(x>=n)
 89     {
 90         return ;
 91     }
 92     int temp[10][10];
 93     memcpy(temp,mayan,sizeof(temp));
 94     for(int i=0;i<5;i++)
 95     {
 96         for(int j=0;j<7;j++)
 97         {
 98             if(!mayan[i][j])
 99             {
100                 continue;
101             }
102             if(i!=4)
103             {
104                 swap(mayan[i][j],mayan[i+1][j]);
105                 fell_down(i);
106                 fell_down(i+1);
107                 clear();
108                 new_ans(x+1,i,j,1);
109                 dfs(x+1);
110                 new_ans(x+1,0,0,0);
111                 memcpy(mayan,temp,sizeof(mayan));
112             }
113             if(i&&!mayan[i-1][j]) 
114             {
115                 swap(mayan[i][j],mayan[i-1][j]);
116                 fell_down(i);
117                 fell_down(i - 1);
118                 clear();
119                 new_ans(x+1,i,j,-1);
120                 dfs(x + 1);
121                 new_ans(x+1,0,0,0);
122                 memcpy(mayan,temp,sizeof(mayan));
123             }
124         }
125         
126     }
127 }
128 int main()
129 {
130     cin>>n;
131     for(int i=0;i<5;i++)
132     {
133         int p=0;
134         do
135         {
136             cin>>mayan[i][p];
137             p++;
138         }while(mayan[i][p-1]!=0);
139     }
140     dfs(0);
141     if(xxx!=1)
142     {
143         cout<<-1<<endl;
144     }
145 }

拓展：剪枝

DFS专用，BFS就不用想了。
可行性剪枝：如果已经判断这下面的都不合法，就可以剪枝。
最优性剪枝：如果下面的答案一定不会比当前更优，剪枝
搜索的顺序对剪枝会有很大影响。

一些好到无话可说的好题目：

NOIP2015 斗地主

如果当前的出牌数已经超过了最优的ans，剪枝（最优性剪枝）
搜索顺序：先顺子，之后就不用记录牌的大小了，只要记录张数有1,2,3,4的分别有几种就可以了。
之后先打牌数多的，先打四带二，再打三带一，也就是说一旦打出三代一，以后就不可能打出四带二了。
每次搜索开始时，用当前的出牌数加上不同点数的牌的数量更新ans。

代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 int ans=0x7fffffff;
  7 int n,m,sum[20];
  8 int T;
  9 void DFS(int x)
 10 {
 11     if(x>=ans)//Ë³×Ó 
 12     {
 13         return ;
 14     }
 15     int k=0;//µ¥Ë³×Ó 
 16     for(int i=3;i<=14;i++)
 17     {
 18         if(sum[i]==0)
 19         {
 20             k=0;
 21         }
 22         else
 23         {
 24             k++;
 25             if(k>=5)
 26             {
 27                 for(int j=i;j>=i-k+1;j--)
 28                 {
 29                     sum[j]--;
 30                 }
 31                 DFS(x+1);
 32                 for(int j=i;j>=i-k+1;j--)
 33                 {
 34                     sum[j]++;
 35                 }
 36             }
 37         }
 38     }
 39     k=0;//Ë«Ë³×Ó 
 40     for(int i=3;i<=14;i++)
 41     {
 42         if(sum[i]<=1)
 43         {
 44             k=0;
 45         }
 46         else
 47         {
 48             k++;
 49             if(k>=3)
 50             {
 51                 for(int j=i;j>=i-k+1;j--)
 52                 {
 53                     sum[j]-=2;
 54                 }
 55                 DFS(x+1);
 56                 for(int j=i;j>=i-k+1;j--)
 57                 {
 58                     sum[j]+=2;
 59                 }
 60             }
 61         }
 62     }
 63     /*k=0;//ÈýË³×Ó 
 64     for(int i=3;i<14;i++)
 65     {
 66         if(sum[i]<=2)
 67         {
 68             k=0;
 69         }
 70         else
 71         {
 72             k++;
 73             if(k>=2)
 74             {
 75                 for(int j=i;j>=i-k+1;j--)
 76                 {
 77                     sum[j]-=3;
 78                 }
 79                 DFS(x+1);
 80                 for(int j=i;j>=i-k+1;j--)
 81                 {
 82                     sum[j]+=3;
 83                 }
 84             }
 85         }
 86     }*/
 87     for(int i=2;i<=14;i++)//´øÅÆ 
 88     {
 89         if(sum[i]<=3)
 90         {
 91             if(sum[i]<=2)
 92             {
 93                 continue;
 94             }
 95             sum[i]-=3;
 96             for(int j=2;j<=15;j++)
 97             {
 98                 if(sum[j]<=0||j==i)
 99                 {
100                     continue;
101                 }    
102                 sum[j]--;
103                 DFS(x+1);
104                 sum[j]++;
105             }
106             for(int j=2;j<=14;j++)
107             {
108                 if(sum[j]<=1||j==i)
109                 {
110                     continue;
111                 }
112                 sum[j]-=2;
113                 DFS(x+1);
114                 sum[j]+=2;
115             }
116             sum[i]+=3;
117         }
118         else
119         {
120             sum[i]-=3;
121             for(int j=2;j<=15;j++)
122             {
123                 if(sum[j]<=0||j==i)
124                 {
125                     continue;
126                 }    
127                 sum[j]--;
128                 DFS(x+1);
129                 sum[j]++;    
130             }
131             for(int j=2;j<=14;j++)
132             {
133                 if(sum[j]<=1||j==i)
134                 {
135                     continue;
136                 }
137                 sum[j]-=2;
138                 DFS(x+1);
139                 sum[j]+=2;
140             }
141             sum[i]+=3;
142             sum[i]-=4;
143             for(int j=2;j<=15;j++)
144             {
145                 if(sum[j]<=0||j==i)
146                 {
147                     continue;
148                 }
149                 sum[j]--;
150                 for(int k=2;k<=15;k++)
151                 {
152                     if(sum[k]<=0||k==j)
153                     {
154                         continue;
155                     }
156                     sum[k]--;
157                     DFS(x+1);
158                     sum[k]++;
159                 }
160                 sum[j]++;
161             }
162             for(int j=2;j<=14;j++)
163             {
164                 if(sum[j]<=1||j==i)
165                 {
166                     continue;
167                 }
168                 sum[j]-=2;
169                 for(int k=2;k<=14;k++)
170                 {
171                     if(sum[k]<=1||j==k)
172                     {
173                         continue;
174                     }
175                     sum[k]-=2;
176                     DFS(x+1);
177                     sum[k]+=2;
178                 }
179                 sum[j]+=2;
180             }
181             sum[i]+=4;
182             
183         }
184     }
185     for(int i=2;i<=15;i++)
186     {
187         if(sum[i])
188         {
189             x++;
190         }
191     }
192     ans=min(ans,x);
193 }
194 int main()
195 {
196     cin>>T>>n;
197     while(T--)
198     {
199         ans=0x7fffffff;
200         int x,y;
201         memset(sum,0,sizeof(sum));
202         for(int i=1;i<=n;i++)
203         {
204             cin>>x>>y;
205             if(x==0)
206             {
207                 sum[15]++;
208             }
209             else
210             if(x==1)
211             {
212                 sum[14]++;
213             }
214             else
215             {
216                 sum[x]++;
217             }
218         }
219         //cout<<ans<<endl;
220         DFS(0);
221         cout<<ans<<endl;
222     }
223     return 0;
224 }

2.切蛋糕（IOI 1999）

这是道名题啊！！！！！

IOI啊！！！！

不过也确实时20年前的题目了，要是放到现在，那想游客这样的大佬也不会天天说AKIOI了，但在当年确实怪难，那剪枝，鬼畜。

搜索顺序：从最下面一层开始，一层一层向上搜，枚举最下面的半径和高度最大。
以算好的答案（最小面积）减去蛋糕当前层以下的总面积若小于上面所能构成的最小面积，就剪枝（最优性剪枝）
总体积减去当前层以下的总体积小于上面所能构成的最小体积，剪枝（可行性剪枝）

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=30;
 6 int roun[maxn];
 7 int high[maxn];
 8 int n,m;
 9 int minn=0x7fffffff;
10 void dfs(int x,int y,int k,int z)
11 {
12     if(y<0)
13     {
14         //cout<<111111<<endl;
15         return ;
16     }
17     if(k>=minn)
18     {
19     //    cout<<22222<<endl;
20         return ;
21     }
22     if(x>m+1)
23     {
24         //cout<<33333<<endl;
25         return ;
26     }
27     if(y==0&&x==m+1)
28     {
29         k=k+roun[1]*roun[1];
30         if(k<minn)
31         {
32             minn=k;
33         }
34         //cout<<44444<<endl;
35         return ;
36     }
37     if(k+z+roun[1]*roun[1]>minn)
38     {
39         //cout<<55555<<endl;
40         return ;
41     }
42     if(y-(roun[x-1])*(roun[x-1])*(high[x-1])*z>0)
43     {
44         //cout<<6666<<endl;
45         return ;
46     }
47     for(int i=roun[x-1]-1;i>=z;i--)
48     {
49         for(int j=high[x-1]-1;j>=z;j--)
50         {
51             if(y-i*j*i>=0&&x+1<=m+1)
52             {
53                 roun[x]=i;
54                 high[x]=j;
55                 dfs(x+1,y-i*i*j,k+(2*i*j),z-1);
56                 high[x]=0;
57                 roun[x]=0;
58                 //cout<<111111<<endl;
59                 
60             }
61         }
62     }
63 }
64 int main()
65 {
66     cin>>n>>m;
67     roun[0]=(int )sqrt(n);
68     high[0]=(int )sqrt(n);
69     dfs(1,n,0,m);
70     if(minn==0x7ffffff)
71     {
72         cout<<"0"<<endl;
73     }
74     else
75     {
76         cout<<minn<<endl;
77     }
78     
79     return 0;
80 }

3.小木棍（加强版）

这是一个好题目，那个天天AKIOI的游客（因为是机房大佬，所以不得不膜）竟然运用运动会的时间，花了一下午没打出来，真好奇他当时有没有对电脑进行了某种报复行为。。。。

暴力思路，一个一个枚举长度x，看能不能填满sum/x根木棍。
剪枝1：X必须是sum的因数，且X>=maxlen。
剪枝2：将木棍降序排列，优先填更长的。
剪枝3：开始搜索一根新木棒时，如果用第一根未填过的木棍填充就已经失败，那一定会失败。
剪枝4：多根木棍一样时，一根失败，后面全部跳过。
剪枝5：因为答案限制了一个最长值，这一个东西卡死了好多书上的标称。
后话：这题蓝书上的程序过不了，本来机房大佬都做好了变棕的准备，然后发现过不了。。。。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 using namespace std;
 6 int minn,maxx;
 7 int n,m;
 8 const int maxn=1e6+10;
 9 int tim[maxn];
10 int tot,cnt;
11 void dfs(int ans,int sum,int flag,int p)
12 {
13     if(ans==0)
14     {
15         cout<<flag<<endl;
16         exit(0);
17     }
18     if(sum==flag)
19     {
20         dfs(ans-1,0,flag,maxx);
21         return ;
22     }
23     for(int i=p;i>=minn;i--)
24     {
25         if(i+sum<=flag&&tim[i])
26         {
27             tim[i]--;
28             dfs(ans,sum+i,flag,i);
29             tim[i]++;
30             if(sum==0||i+sum==flag)
31             {
32                 break;
33             }
34         }
35         
36     }
37     return ;
38 }
39 int main()
40 {
41     cin>>n;
42     minn=n;
43     int m;
44     while(n--)
45     {
46         cin>>m;
47         if(m<=50)
48         {
49             tot++;
50             tim[m]++;
51             cnt+=m;
52             maxx=max(maxx,m);
53             minn=min(minn,m);
54         }
55         
56     }
57     m=cnt>>1;
58     for(int i=maxx;i<=m;i++)
59     {
60         if(cnt%i==0)
61         {
62             
63             dfs(cnt/i,0,i,maxx);
64         }
65     }
66     cout<<cnt<<endl;
67     return 0;
68 }

不得不说满眼的绿色还挺舒服的。。。。