2015
05-23

# 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.

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
Hintavoid enormous arrays or lists, if possible. 

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;
}