uva 10404 Bachet's Game(完全背包）

题目连接：10404 - Bachet's Game

题目大意：由一堆石子，给出石子的总数，接下来由stan和ollie两个人玩游戏，给出n，在给出n种取石子的方法（即为每次可取走石子的数量），由stan先，两人轮流取走石子，最后一个将石子全部去完的人胜利，问，给出的一堆石子，两人均按最好的方案游戏，最后将会是谁胜？

解题思路：问题可以看做是一个完全背包的变形， dp[i]只有0 和1两种状态， 1 是代表当前i个石子先取者为必胜， 0 带表当前n个石子先取者为必败。转态转移方程if (dp[i - val[j]] == 0) dp[i] = 1;(当前状态可以转化成先手必败，说明当前为先手必胜）。

#include <stdio.h>

#include <string.h>

const int N = 1000005;

int n, m, dp[N], val[20];

int main() {

    while (scanf("%d%d", &n, &m) == 2) {

	memset(dp, 0, sizeof(dp));

	memset(val, 0, sizeof(val));

	for (int i = 0; i < m; i++)

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

	for (int i = 1; i <= n; i++) {

	    for (int j = 0; j < m; j++)

		if (i - val[j] >= 0 && !dp[i - val[j]]) {

		    dp[i] = 1;

		    break;

		}

	}

	printf("%s\n", dp[n] ? "Stan wins" : "Ollie wins");

    }

    return 0;

}

巴特西

uva 10404 Bachet's Game(完全背包）

最新文章

热门文章