uva10404 Bachet’s Game（dp之取石子儿游戏的胜负）

Bachet’s game is probably
known to all but probably
not by this name. Initially
there are n stones on the table. There are two players
Stan and Ollie, who move alternately. Stan always starts.
The legal moves consist in removing at least one but not
more than k stones from the
table. The winner is the one to take the last stone.
Here we consider a variation of this game. The number of stones that can be removed in a single
move must be a member of a certain set of m numbers. Among the m numbers there is always 1 and
thus the game never stalls.
Input
The input consists of a number of lines. Each line describes one game by a sequence of positive numbers.
The first number is n 1000000 the number of stones on the table; the second number is m 10 giving
the number of numbers that follow; the last m numbers on the line specify how many stones can be
removed from the table in a single move.
Output
For each line of input, output one line saying either ‘Stan wins’ or ‘Ollie wins’ assuming that both
of them play perfectly.
Sample Input
20 3 1 3 8
21 3 1 3 8
22 3 1 3 8
23 3 1 3 8
1000000 10 1 23 38 11 7 5 4 8 3 13
999996 10 1 23 38 11 7 5 4 8 3 13
Sample Output
Stan wins
Stan wins
Ollie wins
Stan wins
Stan wins
Ollie wins
题意是：给出n个石子，先手，后手在这里取石子，但是和经典的取石子游戏不同的是，这里每个人每次可以取的石子的数量是有限制的，即长度为m的数组的一个元素，现在问你先手可不可以赢。
定义 dp[i]:当玩家面对，剩余i个石子的时候，他的输赢状况，1表示赢，0表示输，
状态的转移是：dp[i]=dp[ i - a[j] ] ,(0<=j < m, i - a [j]>=0)
所以答案是dp[n]：即当先手面对剩余n个石子的时候的输赢的状况

#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<cstring>
#include<stack>
#include<string>
#include<set>
#include<fstream>
using namespace std;
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))
#define bug printf("===\n");
#define rep(a,b) for(int i=a;i<b;i++)
#define rep_(a,b) for(int i=a;i<=b;i++)
#define P pair<int,int>
#define X first
#define Y second
#define vi vector<int>
const int maxn=1000002;
const int inf=999999999;
typedef long long LL;
void Max(int&a,int b){if(a<b)a=b;}

int a[15];
int dp[maxn];

int main(){
    int n,m;
    while(~scanf("%d",&n)){
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
        }
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=0;
            for(int j=0;j<m;j++)if(i-a[j]>=0&&!dp[i-a[j]]){
                dp[i]=1;break;
            }
        }

        if(dp[n]){
            puts("Stan wins");
        }
        else {
            puts("Ollie wins");
        }
    }
    return 0;
}


/*

20 3 1 3 8
21 3 1 3 8
22 3 1 3 8
23 3 1 3 8
1000000 10 1 23 38 11 7 5 4 8 3 13
999996 10 1 23 38 11 7 5 4 8 3 13
*/