uva 279 - Spin(递推)

题目链接：uva 279 - Spin

题目大意：进行一个游戏，给出初始状态，要求问说最少多少步可以让所有的环移动出来。移动规则如图所示。

解题思路：一开始以为是隐式图搜索，写完TLE了。后来发现这道题和汉诺塔是一个思路，都是采取最优策略，并且说左边环的状态不会影响右边环。所以dp[i]表示从右边数，第i个为v，其他均为h的步数（由全h变换至）。
模拟最优过程有dp[i]=dp[i−1]∗2+i∗2−1
对已给定状态，可看做由全h变换到该状态的步数。根据容斥原理，第奇数个v为加，偶数个v为减。最后还要考虑到pos。

C++ TLE
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 50;
const ll mod = 30;

struct state {
    ll s, c;
    state (ll s, ll c) {
        this->s = s;
        this->c = c;
    }
};
int n, k;

inline bool ispos (ll pos, ll s) {
    if (pos >= n)
        return true;
    return !(s & (1<<pos));
}

inline ll cal (char* str, ll pos) {
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        if (str[i] == 'v')
            ans |= (1<<i);
    }
    return ans * mod + pos;
}

ll bfs (ll S) {
    queue<state> que;
    que.push(state(S, 0));

    map<ll, int> g;
    g[S] = 1;

    while (!que.empty()) {
        state u = que.front();
        que.pop();
        //printf("%lld %lld\n", u.s, u.c);

        if (u.s == 0)
            return u.c + 2;

        ll pos = u.s % mod, s = u.s / mod;

        // left;
        if (pos > 0 && ispos(pos + 1, s) ) {
            ll v = s * mod + pos - 1;

            if (!g.count(v)) {
        //        printf("left!\n");
                g[v] = 1;
                que.push(state(v, u.c+1));
            }
        }

        // right;
        if (pos < n-1 && (pos >= n - 2 || (ispos(pos + 2, s) && ispos(pos + 3, s))) ) {
            ll v = s * mod + pos + 1;

            if (!g.count(v)) {
        //        printf("rignt!\n");
                g[v] = 1;
                que.push(state(v, u.c+1));
            }
        }

        if ( pos == n-1 || !ispos(pos+1, s)) {
            ll v = (s^(1<<pos)) * mod + pos;

            if (!g.count(v)) {
        //        printf("change!\n");
                g[v] = 1;
                que.push(state(v, u.c+1));
            }
        }
    }
    return -1;
}

int main () {
    int pos, cas;
    char str[maxn];
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%s%d", &n, str, &pos);
        printf("%lld\n", bfs(cal(str, pos-1)));
    }
    return 0;
}

C++ AC
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 30;


int main () {
    int cas, n;
    ll pos, dp[maxn+5];
    char str[maxn+5];

    dp[0] = 0;
    for (int i = 1; i <= maxn; i++)
        dp[i] = (dp[i-1] + i) * 2 - 1;

    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%s%lld", &n, str, &pos);
        ll ans = 0, sign = 1;
        for (int i = 0; i < n; i++) {
            if (str[i] == 'v') {
                ans += (sign * dp[n-i]);
                sign *= -1;
            }
        }
        printf("%lld\n", ans + pos + 1);
    }
    return 0;
}