#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int M = 1<<19; int dp[M+5]; int a[20]; int getk(int st,int x){//去除x的倍數(shù)及不在集合中組成的和在集合中for(int i = x;i <= 20;i+=x)st &= ~(1<<(i-2));//去除x的倍數(shù)；for(int i = 2;i <= 20;i++){if(st&(1<<(i-2))){for(int j = x;i-j-2 >= 0;j+=x){if(!(st&(1<<(i-j-2)))){st &= ~(1<<(i-2));break;}}}}return st; } int dfs(int st){if(dp[st] != -1) return dp[st];for(int i = 2;i <= 20;i++){if(st&(1<<(i-2))){int k = getk(st,i);if(!dfs(k)) return dp[st] = 1;}}return dp[st] = 0; } int main(){memset(dp,-1,sizeof(dp));dp[0] = 0;int n,t,S = 1;cin >> t;while(t --){int st = 0;cin >> n;for(int i = 0;i < n;i++){cin >> a[i];st |= (1<<(a[i]-2));//總的狀態(tài)}printf("Scenario #%d:\n",S++);if(dfs(st) == 0) cout << "There is no winning move." << endl;else {cout << "The winning moves are:" ;for(int i = 0;i < n;i++){int k = getk(st,a[i]);if(!dfs(k)) cout<< " " << a[i];}cout << "." <<endl;}cout << endl;} }
題意：給你n個(gè)數(shù) ?n個(gè)數(shù) 在2~19范圍內(nèi)，兩個(gè)人每個(gè)人取一個(gè)數(shù)，去除其倍數(shù)以及不在集合中兩個(gè)數(shù)的和，誰先取完，誰就獲勝，求第一個(gè)人獲勝取得第一個(gè)數(shù)是什么（可以是多個(gè)）

題解：記憶化搜索 + 狀態(tài)壓縮??

??

總結(jié)

以上是生活随笔為你收集整理的zoj - 1039 Number Game的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。