UVa 10651 Pebble Solitaire（状态压缩DP）

题意：

类似于跳棋，当两颗石子左或者右有空位置时，移动。每次转移之后移去经过的石子。

思路：

有12个格子，所以状态最多有2^12=4096个。把每次搜索过的状态存在dp[]数组中，以后再次查询类似的直接返回即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define min(a,b) (((a) < (b)) ? (a) : (b))

int dp[4100];

int solve(int n)
{
    if (dp[n] != -1)
        return dp[n];

    dp[n] = 0;
    for (int i = 0; i < 12; ++i)
        if (n & (1 << i))
            dp[n] += 1;

    for (int i = 0; i < 10; ++i)
    {
        int t;
        if ((n&(1<<i)) && (n&(1<<(i+1))) && !(n&(1<<(i+2))))
        {
            t = n;
            t &= ~(1 << i);
            t &= ~(1 << (i+1));
            t |= 1 << (i+2);
            dp[n] = min(dp[n], solve(t));
        }

        if (!(n&(1<<i)) && (n&(1<<(i+1))) && (n&(1<<(i+2))))
        {
            t = n;
            t &= ~(1 << (i+1));
            t &= ~(1 << (i+2));
            t |= 1 << i;
            dp[n] = min(dp[n], solve(t));
        }
    }
    return dp[n];
}

int main()
{
    memset(dp, -1, sizeof(dp));

    int cases;
    scanf("%d", &cases);
    while (cases--)
    {
        char str[20];
        int n = 0;

        scanf("%s", str);
        for (int i = 0; i < 12; ++i)
            if (str[i] == 'o')
                n ^= 1 << i;

        printf("%d\n", solve(n));
    }
    return 0;
}