http://poj.org/problem?id=3688

从i=0开始,画一颗必胜/必败态的转移树,不难分析出:
如果W只能表示成奇数个数字之和,则先手必胜。
如果W只能表示为偶数个数字之和,则后手必胜。
如果W可以表示为奇数个或偶数个数字之和,则谁胜利都有可能。

转移方程:
dp[j][1] = dp[j - a[i]][0]
dp[j][0] = dp[j - a[i]][1]

最后判断:if (dp[i][1] && !dp[i][0]) ++ans;

/*2579ms,432KB*/

int a[10005];
bool dp[100005][2]; /// dp[W][1]=true表示W可以分解成奇数个数,dp[W][0]=true表示W可以分解成偶数个数

int main()
{
    int n, m, i, j, ans;
    while (SII(n, m), n)
    {
        SA(a, i, n); 
        sort(a, a + n);
        mem(dp, 0), dp[a[0]][1] = true;
        Forr(i, 1, n)
        {
            rForr(j, m, a[i])
            {
                if (dp[j - a[i]][0]) dp[j][1] = true;
                if (dp[j - a[i]][1]) dp[j][0] = true;
            }
            dp[a[i]][1] = true;
        }
        int ans = 0;
        Forr(i, 1, m + 1) if (dp[i][1] && !dp[i][0]) ++ans;
        PI(ans);
    }
    return 0;
}

Comments

comments powered by Disqus