博弈的基礎題，通過求SG值，注意一點的是別忘了用記憶化搜索優化，否則容易TEL...
http://acm.hdu.edu.cn/showproblem.php?pid=1536
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 #include <bitset>
5
6 using namespace std;
7 vector<int> s;
8 int dp[10006];
9 int dfs(int v)
10 {
11 bitset<300> hash(0);
12 for(int i=0;i<s.size();i++){
13 if(v-s[i]>=0){
14 if(dp[v-s[i]]==-1){
15 dp[v-s[i]]=dfs(v-s[i]);
16 }
17 hash.set(dp[v-s[i]]);
18 }
19 else break;
20 }
21 for(int i=0;i<300;i++)
22 if(hash.test(i)==0)return i;
23 }
24
25 int main()
26 {
27 int k;
28 while(scanf("%d",&k)!=EOF,k){
29 s.clear();
30 s.reserve(105);
31 int n;
32 while(k--){
33 scanf("%d",&n);
34 s.push_back(n);
35 }
36 memset(dp,-1,sizeof(dp));
37 sort(s.begin(),s.end());
38 scanf("%d",&n);
39 while(n--){
40 int m;
41 int sg=0;
42 scanf("%d",&m);
43 while(m--){
44 int v;
45 scanf("%d",&v);
46 if(dp[v]==-1)
47 dp[v]=dfs(v);
48 sg^=dp[v];
49 }
50 printf(sg?"W":"L");
51 }
52 printf("\n");
53 }
54 return 0;
55 }
posted on 2008-07-23 20:54
小果子 閱讀(470)
評論(0) 編輯 收藏 引用