POJ 2068 NIm (dp博弈，每个人都有特定的取最大值）

题目大意：

有2n个人，从0开始编号，按编号奇偶分为两队，循环轮流取一堆有m个石子的石堆，偶数队先手，每个人至少取1个，至多取w[i]个，取走最后一个石子的队伍输。问偶数队是否能赢。

分析：

题目数据不大很容易就可以联想到DP博弈，设dp[i][j]表示轮到第i个人，还有j个石子的情况下他所属队伍是否能赢。
那么如果存在一个x，使第i个人取了x个石子后第(i+1)%2n个人无论如何都败，那么他就可以赢；若不存在则输。即是：
dp[i][j]=(dp[(i+1)%2n][j-1]&dp[(i+1)%2n][j-2]&……&dp[(i+1)%2n][j-w[i]])^1;
由于有循环，所以直接dp不好做，改用记忆化搜索。

#include<stdio.h>

#include<string.h>

int dp[][],a[],n;

int dfs(int id , int val)

{

   if(val==)

    return dp[id][val]=;

    if(dp[id][val]!=-)

    return dp[id][val];

    dp[id][val]=;

    for(int i= ; i<=a[id] ; i++)

    {

        if(val<i)

        break;

        if(!dfs((id+)%(*n),val-i))

         dp[id][val]=;

    }

    return dp[id][val];

}

int main( )

{

    int m;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==)

        break;

        scanf("%d",&m);

        for(int i= ; i<*n ; i++)

        scanf("%d",&a[i]);

        memset(dp,-,sizeof(dp));

        printf("%d\n",dfs(,m));

    }

}

巴特西

POJ 2068 NIm (dp博弈，每个人都有特定的取最大值）

题目大意：

最新文章

热门文章