UVa 10404 Bachet's Game(단순 DP)

제목:
한 무더기의 돌은 두 사람이 매번 X개를 들 수 있고, X는 m가지로 들 수 있다.마지막 돌을 잡은 사람이 이긴다.
아이디어:
간단한 상태로 dp, dp[i]=true는 i개의 돌멩이가 있음을 표시하고 먼저 선택한 사람이 이길 수 있다.

#include <cstdio>

#include <cstdlib>

#include <cstring>



bool dp[1000010];



int main()

{

    int n, m, a[12];

    while (scanf("%d", &n) != EOF)

    {

        scanf("%d", &m);

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

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



        dp[0] = false;

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

        {

            bool flag = false;

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

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

                    flag = true; break;

                }

            dp[i] = flag;

        }

        if (dp[n])

            printf("Stan wins
");

        else

            printf("Ollie wins
");

    }

    return 0;

}