称号：背景：brick game有N块，给你一个整数的定数S，两个人轮流木；

的木块数是集合S中存在的随意数字。取走最后木块的人获胜。无法取则对方获胜。

题干：如今让你先取，给你一个你的结果序列串T，当中第k个字符代表有k个木块时你的结果：

可能赢就是T[k] = W。一定输就是T[k] = L。

问题：请你确定一个最小的集合，使得这个序列串T成立。（集合中元素为不超过20的正整数）

分析：博弈，状态压缩+dp验证。

由于集合最多20个元素，利用20个位表示每一个元素（1~20）的选取状态。

枚举全部可能情况，然后利用dp计算每种情况下的结果序列。推断是否和输入同样就可以。

1.枚举的时候，依照集合元素的递增顺序就可以，那么第一个满足T串的集合就是所求解。

位运算计算全组合C(n,k)代码：

	xx,yy,comb = (1<<k)-1;

	while ( comb < (1<<n) ) {

		//存储相应位的数值

		xx = comb&-comb,yy = comb+xx;

		comb = ((comb&~yy)/xx>>1)|yy;

	}

2.模拟的时候，利用dp求解（类似01背包），假设如今状态是可能赢，那么它之前状态一定输。

所以有状态转移方程：  M[i] = 'W'         存在M[i-S[j]] = ‘L’

M[i] = 'L'          不存在M[i-S[j]] = ‘L’

dp过程代码：

	for ( i = 1 ; i <= L ; ++ i )

	for ( j = 1 ; j <= k ; -- j )

		if ( M[i-S[j]] == 'L' )

			M[i] = 'W';

由于dp过程是按位的长度进行的，能够一边计算一边比較提高效率。

注意：数据中存在“全是'L'的情况，输出长度+1就可以。

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

char T[128],M[128];

int  S[32];

int tests( int n, int L )

{

	int N = (1<<n),k,i,j,count,flag;

	/*全是'L'的情况*/

	int tes = 0;

	for ( k = 1 ; k <= L ; ++ k )

		if ( T[k] == 'W' ) {

			tes = 1; break;

		}

	if ( !tes ) {

		printf(" %d\n",n+1);

		return 1;

	}

	/*存在'W'的情况*/

	/*计算顺序调整。是为了满足题目要求顺序*/

	for ( k = n ; k >= 1 ; -- k ) {

		int xx,yy,comb = (1<<k)-1;

		while ( comb <= N ) {

			/* 计算当前状态相应的集合 */

			j = 0,count = 0;

			do {

				if ( !((1<<j)&comb) ) S[++ count] = n-j;

				j ++;

			}while ( j < n );

			/* dp求解集合可以产生的结果串 */

			flag = 1;

			for ( i = 0 ; i <= L ; ++ i )

				M[i] = 'L';

			for ( i = 1 ; i <= L ; ++ i ) {

				for ( j = count ; j >= 1 ; -- j ) {

					if ( S[j] > i ) break;

					if ( M[i-S[j]] == 'L' )

						M[i] = 'W';

				}

				if ( M[i] != T[i] ) {

					flag = 0;

					break;

				}

			}

			/* 满足题意的解输出 */

			if ( flag ) {

				for ( i = count ; i >= 1 ; -- i )

					printf(" %d",S[i]);

				printf("\n");

				return 1;

			}

			/* 位运算计算下一集合,依照顺序递增 */

			xx = comb&-comb,yy = comb+xx;

			comb = ((comb&~yy)/xx>>1)|yy;

		}

	}

	return 0;

}

int main()

{

	int n;

	while ( ~scanf("%d",&n) )

	for ( int t = 1 ; t <= n ; ++ t ) {

		scanf("%s",&T[1]);

		int L = strlen(&T[1]);

		printf("Case %d:",t);

		tests( min(20,L), L );

	}

	return 0;

}