[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;?
}?
|