UVa 10404 Bachet's Game (DP&博弈)

10404 - Bachet's Game

Time limit: 6.666 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1345

博弈~

规则1：一个状态是必败状态当且仅当它所有后继是必败状态

规则2：一个状态是必胜状态当且仅当它至少有一个后继是必败状态

边界：这一题0是必败状态

思路：从下往上递推，don't you？

PS：递归会爆栈。

完整代码：

/*0.399s*/

#include<bits/stdc++.h>
using namespace std;

bool dp[1000005];
int a[11];

int main()
{
    int n, m, i, j;
    bool flag;
    while (~scanf("%d%d", &n, &m))
    {
        for (i = 0; i < m; ++i)
            scanf("%d", &a[i]);
        sort(a, a + m);
        for (i = 1; i <= n; ++i)
        {
            flag = false;
            for (j = 0; j < m && i >= a[j]; ++j)
                if (!dp[i - a[j]])
                {
                    flag = true;
                    break;
                }
            dp[i] = flag;
        }
        puts(dp[n] ? "Stan wins" : "Ollie wins");
    }
    return 0;
}

作者：csdn博客 synapse7

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， 机器博弈
， 棋类博弈
， int
， 博弈
， 状态
， flag
， 规则
一个
galgame、3dmgame、c5game、战争前线00game、game center，以便于您获取更多的相关知识。