單詞博弈解題思路 文思海輝程式設計大賽

部落格，這裡開始了我人生的又一個有意義的第一次——第一次寫個人部落格。

。。。好吧，主要還是學習如何寫部落格，記錄自己成長的過程，在這裡就記下這題“單詞博弈”解題思路，寫寫個人思路，也非常歡迎江湖有志同道合的朋友共同探讨！

題目詳情

甲乙兩個人用一個英語單詞玩遊戲。兩個人輪流進行，每個人每次從中删掉任意一個字母，如果剩餘的字母序列是嚴格單調遞增的（按字典序a < b < c <....<z)，則這個人勝利。兩個人都足夠聰明（即如果有赢的方案，都不會選輸的方案 ），甲先開始，問他能赢麼？

輸入： 一連串英文小寫字母，長度不超過15,保證最開始的狀态不是一個嚴格單增的序列。

輸出：1表示甲可以赢，0表示甲不能赢。

例如: 輸入 bad， 則甲可以删掉b或者a,剩餘的是ad或者bd，他就赢了，輸出1。

又如: 輸入 aaa， 則甲隻能删掉1個a，乙删掉一個a,剩餘1個a，乙獲勝，輸出0。

題目不難了解，就是一場博弈，看誰先得到必勝态，思路就是去分析目前狀态得到SG函數，如果下一次操作得到的狀态全部是必敗狀态，那麼推出目前狀态即為必勝狀态；否則，如果下次操作得到的狀态中有必勝狀态，那麼目前狀态則定義為必敗狀态，因為操作者可以通過目前狀态到達必勝狀态。 由此，我們可以通過DFS搜尋，從目前狀态出發，預測能得到的狀态有哪些，并嘗試記錄已經求出的狀态，避免重複搜尋，實作記憶化搜尋。這裡，我們注意到字母序列的長度最大為15，是以我們一共會得到2^15種狀态，這樣做的效果很不錯，希望你會喜歡！

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int map[33010];
int wlen;

bool checkUp(int stat,string word)
{
    char ch=123;
    for (int i=0;i<wlen;++i)
    {
        if ((1<<i)&stat)
        {
            if (word.at(wlen-i-1)>=ch)
            {
                return false;
            }
            else
            {
                ch=word.at(wlen-i-1);
            }
        }
    }
    return true;
}

int DFS(int stat,string word)
{
    if (map[stat]>-1)
    {
        return map[stat];
    }
    if (checkUp(stat,word))
    {
        return map[stat]=0;
    }
    int res=1;
    for (int i=0;(1<<i)<=stat;++i)
    {
        if ((1<<i)&stat)
        {
            res&=DFS((1<<i)^stat,word);
        }
    }
    return map[stat]=res^1;
}

class Test {
public:
   static int who (string   word)
    {
    wlen=word.length();
    int stat=(1<<wlen)-1;
    for (int i=0;i<=stat;++i)
    {
        map[i]=-1;
    }
    return DFS(stat,word);
        return 0;
    }
};
//start 提示：自動閱卷起始唯一辨別，請勿删除或增加。
int main()
{   
    cout<<Test::who("Test")<<endl;   
} 
//end //提示：自動閱卷結束唯一辨別，請勿删除或增加。