Alice和Bob

時間限制:?1 Sec??內(nèi)存限制:?128 MB

題目描述

Alice和Bob在玩這樣的一個游戲， 給定大小為K數(shù)組a1，a2，a3……ak。 一開始， 有x枚硬幣， Alice和Bob輪流取硬幣， 每次所取硬幣的枚數(shù)一定要在 a1，a2，a3……ak之中。 每局Alice先取， 取走最后一枚硬幣的一方獲勝。 當(dāng)雙方都采取最優(yōu)策略的時候， 誰會獲勝？ 題目假定a1，a2，a3……ak之中一定有1。

輸入

本題有多組測試數(shù)據(jù)。

每組數(shù)據(jù)第一行是兩個數(shù)x，k。分別代表開局有X個金幣，和大小為K的數(shù)組。

隨后一行是K個數(shù)，表示可以取得數(shù)。

輸出

對于每組數(shù)據(jù)，輸出贏家是誰

樣例輸入

4 3 1 3 4 9 3 1 3 4

樣例輸出

Alice Bob #include<bits/stdc++.h> using namespace std; #define MAX 10009 bool win[MAX]; int main() {ios::sync_with_stdio(false);int x,k,a[110];while(cin>>x>>k){//分別代表開局有X個金幣，和大小為K的數(shù)組。for(int i=0;i<k;i++)cin>>a[i];win[0]=0;//金幣個數(shù)為0時，先手必敗for(int j=1;j<=x;j++)//枚舉所有金幣{win[j]=0;for(int i=0;i<k;i++){//枚舉所有一次可取的個數(shù)//當(dāng)j>=a[i]時，只要有一個a[i],使得j-a[i]為必敗態(tài)，那么j就為必勝態(tài)；if(j>=a[i]&&!win[j-a[i]])win[j]=1;}}if(win[x]) printf("Alice\n");else printf("Bob\n");}return 0;}

?

總結(jié)

以上是生活随笔為你收集整理的动态规划下的巴什博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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