10404:Bachet's Game

問題文
http://uva.onlinejudge.org/external/104/10404.html

StanとOllieが石をnum[ i ]個ずつ取っていって最後のひとつを取ったほうが勝ち。どちらが勝つか判定せよ。

蟻本4-2章そのまま。

解きなおした。
dp[ 残っている石の個数 ] := 勝敗

dp[ 0 ] = 負け
dp[ i ] = !dp[ i - num[ j ] ]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){
	
	int n,m;
	while(cin >> n >> m){
		vector<int>num(m);
		for(int i=0;i<m;i++)cin >> num[i];
		
		bool dp[1000001];
		fill(dp,dp+1000001,false);
		
		for(int i=1;i<=n;i++)
			for(int j=0;j<m;j++)
				dp[i]|= num[j]<=i && !dp[i-num[j]];
		
		if(dp[n])cout << "Stan wins" << endl;
		else cout << "Ollie wins" << endl;
	}
	return 0;
}