UVA Bachet's Game(10404)

题目大意：

      Stan和Ollie玩一个游戏，有N个石子，Stan先手，两人每次可以从石堆中拿走m个石子，谁拿最后一手，谁赢。其中m的值有范围，每个案例中都设定了m的取值，每次取走石子的个数只能在设定的值中选取，比如一个案例为：21 3 1 3 8，表示石堆中有21个石子，m值可选取的值有3个，分别为1，3和8，也就是每次拿走的石子个数要么是1个，要么是3个，要么就是8个。

 

解题思路：

        动态规划，0-1背包问题，设定dp[i]表示剩下石子个数为 i 时是谁赢，1表示Stan赢，0表示Ollie赢，则状态转移方程的思路就是当 dp[ i - m ] = 0 时，表示当石子剩下 i-m 时，Ollie赢，可以知道当石子为 i 时，就是Stan赢，所以得到方程：

if( i > m && dp[i-m] == 0 )    

dp[i] = 1;

注意：这里的dp范围要取大一些，否则会溢出；

 

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

long long dp[50000000];
int main()
{
	freopen( "test.txt", "r", stdin );

	long long N, M, value;
	vector<long long> v;
	while( cin>>N>>M )
	{
		memset( dp, 0, sizeof(dp) );
		for( int i = 0; i < M; i++ )
		{
			cin>>value;
			v.push_back(value);
		}

		for( int i = 1; i <= N; i++ )
		{
			for( int j = 0; j < M; j++ )
			{
				if( i >= v[j] && dp[ i - v[j] ] == 0 )   // 如果i-v[j]是O最后一手拿的话，那么dp[i-v[j]] 为 0，即S输，但可以知道，若i-v[j]是O最后一手拿，则还剩下v[j]个石子，可知S可以全部拿走，则S赢，所以dp[i] = 1;
				{
					dp[i] = 1;
					break;
				}
			}
		}

		if( dp[N] )
			cout<<"Stan wins"<<endl;
		else
			cout<<"Ollie wins"<<endl;

		v.clear();

	}

	return 0;
}