POJ 3688 博弈与背包

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1E5 + 10;
int inp[maxn], dp[maxn][2], n, m;
int main(int argc, char const *argv[])
{
	while (~scanf("%d%d", &n, &m) && n + m)
	{
		for (int i = 0; i < n; i++)
			scanf("%d", &inp[i]);
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; i++)
		{
			for (int j = m; j > inp[i]; j--)
			{
				if (dp[j - inp[i]][0]) dp[j][1] = true;
				if (dp[j - inp[i]][1]) dp[j][0] = true;
			}
			dp[inp[i]][1] = true;
		}
		int ans = 0;
		for (int i = 1; i <= m; i++)
			if (dp[i][1] && !dp[i][0])
				ans++;
		printf("%d\n", ans);
	}
	return 0;
}

如果石头数可以被偶数张卡片组和而成，则有输的可能 如果石头数可以被奇数张卡片组和而成，则有赢的可能 必胜：石头数只由奇数张卡片组和而成 必败：石头数只由偶数张卡片组合而成 平局：任意卡片组合都无法得到石头数 裁判想让先手必胜只需选择根据卡片的组合先手必胜的石头数 dp[i][1] = true表示石头数为i的情况可以由奇数张卡片组成 dp[i][0] = true表示石头数为i的情况可以由偶数张卡片组成 最后计算所有只由奇数张卡片组成的石头数即可