Description
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.
Input
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.
Output
You should output a single line for each game, as shown below, reporting the ordinal for the game and the maximum number of pieces that can be marked during that game.
Sample Input
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
Sample Output
Game 1: 4
Game 2: 6
Game 3: 1
Game 4: 22
Hint
avoid enormous arrays or lists, if possible.
Source
2011 Mid-Central USA Regional Contest
挺好的水题，考察的是状态压缩。
数据范围很小，但延伸出来的状态量非常大。
每个牌子只有取或不取两种情况 很适合二进制压缩。
对抗赛的时候脑残了，居然想分解每个数，然后dfs暴力过，写了两小时，痛苦的不要不要的。
ps：会长说我代码毒瘤，我很郁闷
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<sstream>
#include<string.h>
#include<queue>
#include<functional>
#define LL long long
using namespace std;
vector<int> V[23];
vector<int> puls[23];
int vis[1<<23];//剪枝标记
int the_sum=1<<22;
class node
{
public:
int the_statu,weizhi,ans;//当前状态，拓展到哪个位置，已用卡牌数量
node(int the_statu,int weizhi,int ans):the_statu(the_statu),weizhi(weizhi),ans(ans){}
};
int build(int n)
{
int nows=1<<n;
int after=nows;
int jishuqi=1;
while(n+jishuqi<23)
{
after<<=1;
after|=nows;
jishuqi++;
}
return after;
}
void chushi()//初始化数组；
{
for(int i=1;i<=the_sum;i++)//枚举每个状态
{
int tmp=i;
int k=0;
int sum=0;
int puls_sums=0;
while(tmp)//处理当前状态
{
++k;//代表数字
if(tmp&1)//当前数的二进制最低位为1时
{
sum+=k;//状态数的二进制枚举到了第k位 当前状态所代表的的和+k；
puls_sums++;//记录当前状态用了几张卡牌；
if(sum>22) break;
}
tmp>>=1;//右移一位
}
if(!tmp)
{
V[sum].push_back(i);
puls[sum].push_back(puls_sums);//记录所对应的状态用了几张卡牌
}
}
}
int the_dig[30];
int main()
{
chushi();
int n,m;
int T=0;
while(scanf("%d %d",&n,&m),(n+m))
{
int maxs=0;
memset(the_dig,0,sizeof the_dig);
memset(vis,0,sizeof vis);
for(int i=1;i<=m;i++)
{
scanf("%d",&the_dig[i]);
}
queue<node> Q;
node now(build(n),0,0);//build(n)表示 只能使用从右数 n位的状态
Q.push(now);
while(!Q.empty())
{
now=Q.front();
Q.pop();
maxs=max(maxs,now.ans);
if(now.weizhi>=m) continue;
int now_dig=the_dig[now.weizhi+1];
int sizes=V[now_dig].size();
//cout<<"size:"<<sizes<<endl;
//cout<<"dig:"<<now_dig<<endl;
//cout<<"sum:"<<now.ans<<endl;
for(int j=0;j<sizes;j++)
{
//cout<<"V_stat:"<<V[now_dig][j]<<endl;
if((V[now_dig][j]&now.the_statu)==0)//当前状态和目标数的组成状态按位与等于0l
{
//cout<<"statis:"<<now.the_statu<<endl;
int the_stat=now.the_statu|V[now_dig][j];
if(!vis[the_stat])
{
Q.push(node(the_stat,now.weizhi+1,now.ans+puls[now_dig][j]));
vis[the_stat]=1;
}
}
}
}
printf("Game %d: %d\n",++T,maxs);
}
return 0;
}