hdu4753 Fishhead’s Little Game 状态压缩，总和一定的博弈

此题和UVA 10891 Game of Sum 总和一定的博弈，区间dp是一个道理，就是预处理麻烦

这是南京网络赛的一题，一直没做，今天做了，虽然时间有点长，但是1ac，这几乎是南京现场赛的最后一道正式题了

typedef long long LL;const int INF = 1000000007;const double eps = 1e-10;const int MAXN = 1000010;int into[20][20];int s[12];vector<int>p[25];bool vis[1 << 24];short dp[1 << 24];/**0 1 23 4 56 7 89 10 1112 13 14 1516 17 18 1920 21 22 23*/short dpf(int ss, int last){    if (!last) return 0;    if (vis[ss]) return dp[ss];    vis[ss] = true;    short &ans = dp[ss];    ans = 0;    short tmp = 0;    short tmplast = last;    int nextss;    REP(i, 24)    {        if ( (ss & (1 << i)) == 0)        {            nextss = ss | (1 << i);            tmp = 0;            tmplast = last;            REP(j, p[i].size())            {                if ( (nextss & s[p[i][j]]) == s[p[i][j]] )                    tmp++, tmplast--;            }            tmp += tmplast - dpf(nextss, tmplast);            ans = max(ans, tmp);        }    }    return ans;}void init(){    ///点到边的映射    FE(i, 1, 16)        if (i % 4) into[i][i + 1] = into[i + 1][i] = i - (i / 4) - 1;    FE(i, 1, 12)        into[i][i + 4] = into[i + 4][i] = 12 + i - 1;    ///边到小正方形的映射，以及小正方形到边的映射    CLR(s, 0);    REP(i, 25) p[i].clear();    REP(i, 9)    {        s[i] |= (1 << i);        p[i].push_back(i);        s[i] |= (1 << (i + 3));        p[i + 3].push_back(i);        s[i] |= (1 << (12 + (i / 3) * 4 + i % 3));        p[12 + (i / 3) * 4 + i % 3].push_back(i);        s[i] |= (1 << (13 + (i / 3) * 4 + i % 3));        p[13 + (i / 3) * 4 + i % 3].push_back(i);    }}int win[2];int n, m;int S;int main (){    int x, y, z;    int T;    int nc = 1;    init();    RI(T);    while (T--)    {        CLR(win, 0);        RI(m);        S = 0;        REP(i, m)        {            RII(x, y);            z = into[x][y];            S |= (1 << z);            REP(j, p[z].size())            {                if ((S & s[p[z][j]]) == s[p[z][j]])                    win[i % 2]++;            }        }        printf("Case #%d: ", nc++);        int last = 9 - (win[0] + win[1]);        if (!last)        {            puts(win[0] > 4 ? "Tom200" : "Jerry404");        }        else        {            CLR(vis, 0);            win[m % 2] += dpf(S, last);            if (m % 2 == 0) puts(win[m % 2] > 4 ? "Tom200" : "Jerry404");            else puts(win[m % 2] > 4 ? "Jerry404" : "Tom200");        }    }    return 0;}