首页 > 代码库 > poj 1143 number game

poj 1143 number game

题目比较长,题意不大好理解

现在把题意抽象一下,大概是以下意思:

1.给2~20的数字中的几个数组成数组a,其中是你可以选择的数字;

2.选择的规则如下:

(1).如果选择了某个数字x,则数组a中是其倍数的数字将被划去;

(2).假如数字n在数组a中,若n-x 的值并不在数组a中,则划去n

3.当没有数字可以选取时,则此player失败;

4.让你找出先选的player选择哪个数字可以胜利。若没有选择输出“(所给的一句话)”

 

1.本题说是动态规划,但是在我看来,这道题 没有 状态转移方程,也没有 明显的 状态 需要来表示。状态转移应该就是代码中DP[state]是依赖于上一层的DP[state],这叫状态转移吗?如果算的话应该是最直白的状态转移了,因为没得选择只有一个依赖状态。

2.但是,我觉得这道题目确是实实在在地应用到了 记忆化搜索 的思想。因为当前状态DP[state]的计算需要依赖的上一层状态DP[state]在用到时是没有得出的,是在用到时往下搜索得到的。这里一旦搜过,就用状态DP[state]记录下了该状态下做选择的player能不能胜利(只用01来表示)。

 

3.其实在我看来,这道题目的最大亮点,应该是在上面DP[state]中所提到的这个state ~。这是一种用二进制存储的状态。因为数据范围只到20,而二进制状态存储起码对于31以及以下的数字还是可以存的。而且状态表示起来简单干净,转移起来干脆不拖泥带水。通过这道题很好地学习了二进制状态存取的方法以及位运算的知识。收益很多。

4.代码会好好加注释:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = (1<<21) + 10;

int n;
int a[22],ans[21];
int DP[maxn],vis[maxn];
bool judge(int i,int j,int st){
    return ((((1<<(a[j]-a[i]))&(~st))&&(a[j]-a[i] != 1))||(a[j]%a[i] == 0));
}
int dp(int k,int state){
    if(vis[state]) return DP[state];
    vis[state] = 1;
    if(state == 0) return 0;///没有元素可以选择了,说明本次选择失败返回0;
    if(k == 1) return DP[state] = 1;///只有一个元素可以选择说明成功,返回1;
    for(int i=0;i<n;i++){
        int st = state;
        if((1<<a[i] & st)){///首先选择条件是有这个元素;
        for(int j=i+1;j<n;j++){
            if((1<<a[j]) & st && judge(i,j,st)){
                st ^= (1<<a[j]);
            }
        }
        if(!dp(k-1,st^(1<<a[i]))) return DP[state] = 1;///下一步没有能赢的选择(为0),说明本次选择可以取胜;
        }
    }
    return DP[state] = 0;
}
int main()
{
    int kase = 1;
    while(scanf("%d",&n)!=EOF && n){
        memset(vis,0,sizeof(vis));
        int state = 0;///定义二进制状态存储state;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            state ^= (1<<a[i]);///在读入过程中对状态进行初始化;注意^的作用就是同号为0异号为1;
        }
        sort(a,a+n);///排序,使得小数在前大数在后,方便后面对题目条件的实现;
        int cnt = 0;
        for(int i=0;i<n;i++){
            int st = state;///用另一变量来克隆状态,避免修改根本状态;
            for(int j=i+1;j<n;j++){
                if(judge(i,j,st)){
                    st ^= (1<<a[j]);///这一步的作用就是把原来有的元素去掉,表示此值不能再选;是状态的更新;
                }
            }
            if(dp(n-1,(1<<a[i])^st) == 0){///下一步没有能赢的选择(为0),说明本次选择可以取胜;
                ans[cnt++] = a[i];
            }
        }

        printf("Test Case #%d\n",kase++);
        if(cnt == 0){
            printf("There's no winning move.\n\n");
        }
        else{
            printf("The winning moves are:");
            for(int i=0;i<cnt;i++){
                printf(" %d",ans[i]);
            }
            printf("\n\n");
        }
    }
    return 0;
}


poj 1143 number game