首页 > 搜索 > BFS搜索 > HDU 4212-Shut the Box-位运算-[解题报告]HOJ
2015
05-23

HDU 4212-Shut the Box-位运算-[解题报告]HOJ

Shut the Box

问题描述 :

Shut the Box is a one-player game that begins with a set of N pieces labeled from 1 to N. All pieces are initially "unmarked" (in the picture at right, the unmarked pieces are those in an upward position). In the version we consider, a player is allowed up to T turns, with each turn defined by an independently chosen value V (typically determined by rolling one or more dice). During a turn, the player must designate a set of currently unmarked pieces whose numeric labels add precisely to V, and mark them. The game continues either until the player runs out of turns, or until a single turn when it becomes impossible to find a set of unmarked pieces summing to the designated value V (in which case it and all further turns are forfeited). The goal is to mark as many pieces as possible; marking all pieces is known as "shutting the box." Your goal is to determine the maximum number of pieces that can be marked by a fixed sequence of turns.
As an example, consider a game with 6 pieces and the following sequence of turns: 10, 3, 4, 2. The best outcome for that sequence is to mark a total of four pieces. This can be achieved by using the value 10 to mark the pieces 1+4+5, and then using the value of 3 to mark piece 3. At that point, the game would end as there is no way to precisely use the turn with value 4 (the final turn of value 2 must be forfeited as well). An alternate strategy for achieving the same number of marked pieces would be to use the value 10 to mark four pieces 1+2+3+4, with the game ending on the turn with value 3. But there does not exist any way to mark five or more pieces with that sequence.
Refrigerator Magnets

输入:

Each game begins with a line containing two integers, N, T where 1 ≤ N ≤ 22 represents the number of pieces, and 1 ≤ T ≤ N represents the maximum number of turns that will be allowed. The following line contains T integers designating the sequence of turn values for the game; each such value V will satisify 1 ≤ V ≤ 22. You must read that entire sequence from the input, even though a particular game might end on an unsuccessful turn prior to the end of the sequence. The data set ends with a line containing 0 0.

输出:

Each game begins with a line containing two integers, N, T where 1 ≤ N ≤ 22 represents the number of pieces, and 1 ≤ T ≤ N represents the maximum number of turns that will be allowed. The following line contains T integers designating the sequence of turn values for the game; each such value V will satisify 1 ≤ V ≤ 22. You must read that entire sequence from the input, even though a particular game might end on an unsuccessful turn prior to the end of the sequence. The data set ends with a line containing 0 0.

样例输入:

6 4
10 3 4 2
6 5
10 2 4 5 3
10 10
1 1 3 4 5 6 7 8 9 10
22 22
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
0 0

样例输出:

Game 1: 4
Game 2: 6
Game 3: 1
Game 4: 22
Hint
avoid enormous arrays or lists, if possible.

这题一读完就便可以猜到是搜索题,明显直接暴搜必然超时

由于只有22位,可以用二进制状态储存

可发现状态的转移是固定的,于是乎预处理1~22的所有组合,推荐用vector储存(=。=)

一开始我是dfs+hash来做的,后来超时,显然递归比较慢

后来考虑改成bfs,这个就比较好了。从第一个数的所有组合开始尝试,一个一个数尝试(尝试一个数就是一层),更新ans即可

用bfs的一个好处就是可以用SET代替hash,因为一个状态重复,仅限于尝试bfs的同一层(一个状态的数字和固定嘛)(当然hash+queue应该也行,估计会慢点,没试过)

思路有了就基本可以敲了,可以考虑的优化有几点:

1.初始化只初始N/2,大的数必然是大的数+小的数,或者是小的数+小的数,不可能是大的数+大的数(定义大的数为超过N/2的数)

2.如果某状态能进到下一层,ans就不需要对当前层更新。

3.更多优化待你发现 (= =!)

另外要注意的是位运算的处理方法,不同的处理方法效率也不一样。

附上鄙人丑陋的代码 – -

 #include <iostream>
 #include <vector>
 #include <set>
 #include<cstdio>
 using namespace std;
 vector<int> a[23];
 int ans,nn;
 int b[22];
 int tp=1<<22;
 void init()
 {
     for(int i=1;i<tp;i++)
     {
         int tmp=i;
         int k=0;
         int sum=0;
         while(tmp)
         {
             ++k;
             if(tmp&1)
             {
                 sum+=k;
                 if(sum>22) break;
             }
             tmp>>=1;
         }
         if(!tmp) a[sum].push_back(i);
     }
 }
 
 inline int total_one(int p)
 {
     int c=0;
     while(p)
     {
         p&=p-1;
         c++;
     }
     return c;
 }
 
 int main()
 {
     int T=0;
     int n,m;
     init();
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         if(n+m==0) break;
         nn=1<<n;
         ++T;
         for(int i=0;i<m;i++)
         {
             scanf("%d",&b[i]);
         }
         ans=0;
         set<int> now;
         now.insert(0);
         for(int i=0;i<m;i++)
         {
             set<int> next;
             for(set<int>::iterator it=now.begin();it!=now.end();it++)
             {
                 int temp=a[b[i]].size();
                 int sign=0;
                 int tmp=*it;
                 for(int j=0;j<temp;j++)
                 {
                     if(a[b[i]][j]>=nn) continue;
                     if((tmp & a[b[i]][j]) ==0)
                     {
                         sign=1;
                         next.insert(tmp | a[b[i]][j]);
 //                        int _tmp=total_one(tmp| a[b[i]][j]);
 //                        ans=ans>_tmp?ans:_tmp;
                     }
                 }
                 if(!sign) 
                 {
                     int _tmp=total_one(tmp);
                     ans=ans>_tmp?ans:_tmp;
                 }
             }
             now=next;
             if(now.size()==0) break;
         }            
         for(set<int>::iterator it=now.begin();it!=now.end();it++)
         {
             int _tmp=total_one(*it);
             ans=ans>_tmp?ans:_tmp;
         }
         printf("Game %d: %d\n",T,ans);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/zjh10/articles/2663216.html