uva_10404-Bachet's Game

12-11-15 来源：[db:作者]

收藏我要投稿

[cpp]
/**博弈题。。这种题目的特点就是——想到方法后很简单，想不到
*就做不出了。。开始想穷举法列出所有结果，后来发现数据量太大
*行不通，后来看了看博弈相关东西，突然灵光一闪，想到只考虑当前
*步，把总数为1~count时先手的输赢标记起来，方程为：
* if(i-a[i] == 0 || !num[i-a[i]](i-a[i]>0)) 先手赢
*就是刚好一次可以移动完，或者移动一次后，对手必输
*/
#include
#include
using namespace std;

#define MAX 12
#define MAXC 121

int a[MAX];
int num[MAXC];

void move_stones(int count, int type){
    for(int i = 1; i <= count; i ++){
        for(int j = 0; j < type; j ++){
            if( i - a[j] > 0 && !num[i-a[j]] ){
                num[i] = 1;
                break;
            }else if( i - a[j] == 0 ){
                num[i] = 1;
                break;
            }
        }
    }
    if( num[count] )
        printf("Stan wins\n");
    else
        printf("Ollie wins\n");
}

int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
#endif
    int count, type;
    while( ~scanf("%d", &count) ){
        memset(num, 0, sizeof(num));
        scanf("%d", &type);
        for(int i = 0; i < type; i ++)
            scanf("%d", &a[i]);
        move_stones(count, type);
    }
    return 0;
}

点击复制链接与好友分享!回本站首页