如果硬要說這算是博弈題目的話，那這個博弈是不公平博弈(partizan games)，因為雙方面對同一個局面做出來的決策是不一樣的。

我們平時做的博弈都是公平博弈(impartial games)，所以在這道題里面，那些必勝必敗狀態，SG函數SG定理都派不上用場了。

但是，這道題是可以貪心的。

比如第一個圖案對于Alice來說是安全穩定的，因為Bob不會跟他去搶位置，所以Alice可以省到最后去放。同樣地，Bob可以將第2個圖案省到最后再去放。

比如說第15個圖案，如果能搶先占到的話會很劃算的，因為如果一方占到，不光對方放不了了，自己還會多一個穩定位。

更詳細的分析見這：http://www.cnblogs.com/staginner/archive/2011/09/10/2173317.html

我發現大家的思路都是按照這個來的。

1 #include <cstdio> 2 3 int a[16]; 4 5 int main() 6 { 7 //freopen("in.txt", "r", stdin); 8 9 int T; scanf("%d", &T); 10 for(int kase = 1; kase <= T; ++kase) 11 { 12 for(int i = 1; i <= 15; i++) scanf("%d", &a[i]); 13 int now = 0, A = a[1] * 2, B = a[2] * 2; 14 if(a[15] % 2 != 0) { A++; now = 1; } 15 int ta = a[5] + a[6], tb = a[3] + a[4]; 16 if(ta > tb)//Alice搶5,6, Bob搶3,4 17 { 18 ta -= tb; 19 if(ta % 2 != 0) 20 { 21 if(now == 0) A += ta/2 + 1; 22 else A += ta / 2; 23 now = 1 - now; 24 } 25 else A += ta / 2; 26 } 27 else if(ta < tb) 28 { 29 tb -= ta; 30 if(tb % 2 != 0) 31 { 32 if(now == 0) B += tb / 2; 33 else B += tb/2 + 1; 34 now = 1 - now; 35 } 36 else B += tb / 2; 37 } 38 //兩人瓜分11,12,13,14 39 int t = a[11] + a[12] + a[13] + a[14]; 40 if(t % 2 != 0) now = 1 - now; 41 //Alice搶7,8, Bob搶9,10 42 ta = a[7] + a[8]; tb = a[9] + a[10]; 43 if(ta < tb) 44 { 45 tb -= ta; 46 if(tb % 2 != 0) 47 { 48 if(now == 0) B += tb/2 + 1; 49 else B += tb / 2; 50 now = 1 - now; 51 } 52 else B += tb / 2; 53 } 54 else if(ta > tb) 55 { 56 ta -= tb; 57 if(ta % 2 != 0) 58 { 59 if(now == 0) A += ta / 2; 60 else A += ta/2 + 1; 61 now = 1 - now; 62 } 63 else A += ta / 2; 64 } 65 66 bool win; 67 if(now == 0) win = B >= A ? false : true; 68 else win = A >= B ? true : false; 69 printf("Case #%d: %s\n", kase, win ? "Alice" : "Bob"); 70 } 71 72 return 0; 73 } 代碼君

?

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4418387.html

總結

以上是生活随笔為你收集整理的HDU 4023 (博弈 贪心 模拟) Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。