POJ-1143(状态压缩)

Number Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3432 Accepted: 1399 Description

Christine and Matt are playing an exciting game they just invented: the Number Game. The rules of this game are as follows. The players take turns choosing integers greater than 1. First, Christine chooses a number, then Matt chooses a number, then Christine again, and so on. The following rules restrict how new numbers may be chosen by the two players:

A number which has already been selected by Christine or Matt, or a multiple of such a number,cannot be chosen. A sum of such multiples cannot be chosen, either.

If a player cannot choose any new number according to these rules, then that player loses the game. Here is an example: Christine starts by choosing 4. This prevents Matt from choosing 4, 8, 12, etc.Let’s assume that his move is 3. Now the numbers 3, 6, 9, etc. are excluded, too; furthermore, numbers like: 7 = 3+4;10 = 2*3+4;11 = 3+2*4;13 = 3*3+4;… are also not available. So, in fact, the only numbers left are 2 and 5. Christine now selects 2. Since 5=2+3 is now forbidden, she wins because there is no number left for Matt to choose. Your task is to write a program which will help play (and win!) the Number Game. Of course, there might be an infinite number of choices for a player, so it may not be easy to find the best move among these possibilities. But after playing for some time, the number of remaining choices becomes finite, and that is the point where your program can help. Given a game position (a list of numbers which are not yet forbidden), your program should output all winning moves. A winning move is a move by which the player who is about to move can force a win, no matter what the other player will do afterwards. More formally, a winning move can be defined as follows.

A winning move is a move after which the game position is a losing position. A winning position is a position in which a winning move exists. A losing position is a position in which no winning move exists. In particular, the position in which all numbers are forbidden is a losing position. (This makes sense since the player who would have to move in that case loses the game.) Input

The input consists of several test cases. Each test case is given by exactly one line describing one position. Each line will start with a number n (1 <= n <= 20), the number of integers which are still available. The remainder of this line contains the list of these numbers a1;…;an(2 <= ai <= 20). The positions described in this way will always be positions which can really occur in the actual Number Game. For example, if 3 is not in the list of allowed numbers, 6 is not in the list, either. At the end of the input, there will be a line containing only a zero (instead of n); this line should not be processed. Output

For each test case, your program should output “Test case #m”, where m is the number of the test case (starting with 1). Follow this by either “There’s no winning move.” if this is true for the position described in the input file, or “The winning moves are: w1 w2 … wk” where the wi are all winning moves in this position, satisfying wi < wi+1 for 1 <= i < k. After this line, output a blank line. Sample Input

2 2 5 2 2 3 5 2 3 4 5 6 0 Sample Output

Test Case #1 The winning moves are: 2

Test Case #2 There’s no winning move.

Test Case #3 The winning moves are: 4 5 6 Source

Mid-Central European Regional Contest 2000

题目的意思就是：有一个不到20的数列，两个人一次选择一个数字。选择完一个数字之后，这个数字的倍数，以及这个数字和前面选过的数字之和，都不可以再选。给你一串数列，问你有没有必胜的选择，就是当前选择这个数字之后，无论对方选择什么都是死！！

解题思路：非常像博弈的题目啊，可是这道题目的标签是状态压缩，当然不是我原创的，我一开始也不会啊，看来别人的博客才知道怎么去写。其实看别人博客，也是学习acm的必经之路，不是吗？只是看完之后你得有自己的思考！！ 状态压缩：由于数列不到20，可以用二进制压缩，比如这样一个数列 2 3 5 那么二进制表示就是110100000…. 这样的话，一个数列就可以用一个数字来表示。这就是状态压缩的好处，试想想，没有状态压缩，表示一个数列：234567891011… 或者用一个数组表示。。这些都太麻烦啦。 其次：状态压缩我是可以想到的，但是怎么解决这个问题呢，我一直在想动态规划，每个数列可以用0表示是必胜的数列，1表示不是必胜的数列，然后数列可以逐个递推！对，没错，思路是这样，但是你看代码，其实用深度优先搜索，并没有动态规划的形式，用搜索之所以可以，是因为记忆化搜索，即只要有一个状态确定是0或者1，那么就不用对它进行搜索，这样就会非常快。 动态规划的两种方式实现，一个是递推，另一个就是记忆化搜索。二者都是遍历了所有情况

关于状态压缩和位运算 http://blog.csdn.net/Dacc123/article/details/50974579

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int dp[1<<20];
int n;
int a[25];
int s[25];
//这个函数是把这个二进制数列变成数字，就是将数列压缩成数字来
int getNum(int a[])
{
    int res=0;
    for(int i=2;i<=20;i++)
    {
        if(a[i])
            res|=1;
        res<<=1;
    }
    return res;
}

int dfs(int s[],int st)
{
    int v[25];
    memcpy(v,s,25*sizeof(int));
    v[st]=0;
    //把i的倍数，与之前选过的数字之和，都标记成0
    for(int i=2;i+st<=20;i++)
    {
        if(!v[i])
            v[i+st]=0;
    }
    int ss=getNum(v);
    //记忆化搜索，这里大幅度提高效率
    if(dp[ss]!=0)
    {
        if(dp[ss]>0)
            return 1;
        else
            return 0;
    }
    for(int i=2;i<=20;i++)
    {
        if(v[i]&&!dfs(v,i))
        {
            dp[ss]=1;
            return 1;
        }
    }
    dp[ss]=-1;
    return 0;
}
int main()
{
    int ans[25];
    int b;
    memset(dp,0,sizeof(dp));
    int cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        cas++;
        memset(a,0,sizeof(a));
        if(n==0)
            break;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b);
            a[b]=1;
        }
        int tot=0;
        for(int i=2;i<=20;i++)
        {
            if(a[i]&&!dfs(a,i))
                ans[tot++]=i;
        }
        printf("Test Case #%d\n",cas);
        if(tot==0)
        {
            printf("There's no winning move.\n");

        }
        else
        {
            printf("The winning moves are: ");
            for(int i=0;i<tot;i++)
            {
                if(i!=tot-1)
                    printf("%d ",ans[i]);
                else
                    printf("%d\n",ans[i]);
            }
        }
        printf("\n");


    }
    return 0;
}