程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA10404 Bachet&#39;s Game

UVA10404 Bachet&#39;s Game

編輯：C++入門知識

這題目做的有些較勁，題意：給你n個石頭，Stan跟Ollie按順序取，Stan先手，題目會給你m種取法，每次取石頭的數目必須從這m種中選取一個，假設Stan 和 Ollie 每次的取石頭數目都是最完美的意思就是輸贏一開始就因為取法和石頭數目決定了，不會因為人為原因而影響結果

這題目一看，個人認為是一道博弈的問題，所以開始較勁了，各種尋找sg值的方法，不停的去推去尋找必敗點必勝點，做到後面發現不對勁，每次取石頭取好以後，當前剩余石頭都會有一個固定的狀態，以Stan為基准，那麼這裡0表示Stan必輸，1表示Stan必勝，肯定是有這兩個狀態的，從當前剩余0個石頭的狀態推到當前剩余n的狀態，就知道結果了，這樣以剩余0為邊界條件來dp試試看，最後尋找到了狀態轉移方程

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

//#define ll long long

#define  ll __int64

#define eps 1e-7

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 

int num[12];
int dp[1000000 + 5];

void clear() {
	memset(num,0,sizeof(num));
	memset(dp,0,sizeof(dp));
}

int main() {
	int n,m;
	while(scanf("%d %d",&n,&m) == 2) {
		clear();
		for(int i=0;i= num[j] && dp[i - num[j]] == 0) {
					dp[i] = 1;break;
				}
			}
		}
		if(dp[n])
			puts("Stan wins");
		else
			puts("Ollie wins");
	}
	return EXIT_SUCCESS;
}