hdu 4753 Fishhead’s Little Game

狀態壓縮dp解博弈問題（記憶化搜索）。比賽的時候最後才開始做這道題，而且當時不知道為什麼一直犯一些很2B的問題，導致沒能ac，晚上看了看原先的代碼，改了一下就MLE了。。。我原先是開的dp[1 << 24] 的記憶化數組，果斷超內存了，然後仔細看了一下題目，發現題目中的n >= 12，也就是說用到的狀態不超過2^12個，於是把滿足情況的狀態hash到2^12以內的數組就可以了。                                                                                                因為只有24條邊，所以可以考慮把邊壓縮，於是就轉化成了普通的狀態了，然後用dp數組表示該狀態下先手能得到的最大分值。也就是處於該狀態時，先手放一條邊以後得使得後手得分最少，因為總分是一定的，這樣的話先手就可以得到最優解了。然後就記憶化搜索一下就可以了。我hash用的是數組存儲，二分查找下標的方法，時間效率不是很高。。。    

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<fstream>  
#include<sstream>  
#include<bitset>  
#include<vector>  
#include<string>  
#include<cstdio>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<stack>  
#include<map>  
#include<set>  
#define FF(i, a, b) for(int i=a; i<b; i++)  
#define FD(i, a, b) for(int i=a; i>=b; i--)  
#define REP(i, n) for(int i=0; i<n; i++)  
#define CLR(a, b) memset(a, b, sizeof(a))  
#define debug puts("**debug**")  
#define LL long long  
#define PB push_back  
using namespace std;  
  
const int N= 1 << 13;  
const int INF = 1e9;  
  
int dp[N], n, mp[N];  
int gogo[22][22], num;  
  
void get_gogo()  
{  
    int i , j = 0;  
    for(i = 1; i < 16; i ++)  
    {  
        if(i % 4 == 0) continue;  
        gogo[i][i + 1] = j;  
        j ++;  
    }  
    for(i = 1; i <= 12; i ++)  
    {  
        gogo[i][i + 4] = j;  
        j ++;  
    }  
}  
  
bool ok(int k, int i)  
{  
    return (k & (1 << i)) && (k & (1 << (i + 3))) && (k & (1 << ((i / 3) + i + 12))) && (k & (1 << ((i / 3) + i + 13)));  
}  
  
int get_f(int k)  
{  
    int i, j, ret = 0;  
    for(i = 0; i < 9; i ++)  
    {  
        if((k & (1 << i)) && ok(k, i))  
            ret ++;  
    }  
    return 9 - ret;  
}  
  
int B_ser(int k)  
{  
    int l = 0, r = num - 1, m;  
    while(l <= r)  
    {  
        m = (l + r) >> 1;  
        if(mp[m] == k) return m;  
        else if(mp[m] > k) r = m -1;  
        else l = m + 1;  
    }  
}  
  
int dfs(int mk)  
{  
    int k = mp[mk];  
    if(dp[mk] != -1) return dp[mk];  
    int ret = INF, i;  
    for(i = 0; i < 24; i ++)  
    {  
        if(((1 << i) & k) == 0)  
        {  
            ret = min(ret, dfs(B_ser(k | (1 << i))));  
        }  
    }  
    if(ret == INF)  
    {  
        return dp[mk] = get_f(k);  
    }  
    return dp[mk] = get_f(k) - ret;  
}  
  
int main()  
{  
    //freopen("input.txt", "r", stdin);  
    int a, b, n, u, v, i, j, t, cas = 1, tt, now;  
    get_gogo();  
    scanf("%d", &tt);  
    while(tt --)  
    {  
        scanf("%d", &n);  
        CLR(dp, -1);  
        t = a = b = 0;now = 0;  
        for(i = 0; i < n; i ++)  
        {  
            scanf("%d%d", &u, &v);  
            if(u > v) swap(u, v);  
            int tmd = gogo[u][v];  
            t += (1 << tmd);  
            int kao = 9 - get_f(t);  
            if(i & 1)  
            {  
                b += kao - now;  
                now = kao;  
            }  
            else  
            {  
                a += kao - now;  
                now = kao;  
            }  
        }  
        for(i = t, num = 0; i < (1 << 24); i ++)  
        {  
            if((i & t) == t)  
            {  
                mp[num ++] = i;  
            }  
        }  
        if(n & 1)  
        {  
            b += dfs(0);  
            printf("Case #%d: %s\n", cas ++, b > (9 - b) ? "Jerry404" : "Tom200");  
        }  
        else  
        {  
            a += dfs(0);  
            printf("Case #%d: %s\n", cas ++, a < (9 - a) ? "Jerry404" : "Tom200");  
        }  
    }  
}