https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1592

10651 - Pebble Solitaire.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 10;
const int OO = 1e9;

int n, l;
string s;
int cache[5000];


int getBit(int num, int indx) {
    return ((num>>indx) & 1) == 1;
}

int setBit1(int num, int indx) {
    return num | (1<<indx);
}

int setBit0(int num, int indx) {
    return num & ~(1<<indx);
}

int PebbleSolitaire(int mask) {
    int &ret = cache[mask];
    if(ret != -1)
        return ret;
    ret = 0;
    int tmpmask;
    lp(i, 12-2) {
        tmpmask = mask;
        if(getBit(mask, i) && getBit(mask, i+1) && !getBit(mask, i+2)) {
            tmpmask = setBit0(tmpmask, i);
            tmpmask = setBit0(tmpmask, i+1);
            tmpmask = setBit1(tmpmask, i+2);
            //cout << i << " " << mask << " " << tmpmask << endl;
            ret = max(ret, 1 + PebbleSolitaire(tmpmask));
        }

        if(!getBit(mask, i) && getBit(mask, i+1) && getBit(mask, i+2)) {
            tmpmask = mask;
            tmpmask = setBit1(tmpmask, i);
            tmpmask = setBit0(tmpmask, i+1);
            tmpmask = setBit0(tmpmask, i+2);
            ret = max(ret, 1 + PebbleSolitaire(tmpmask));
        }
    }


    return ret;
}


int main() {
    cin>>n;
    lp(i, n) {
        clr(cache, -1);
        cin>>s;
        int mask = 0;
        l = s.length();
        int cnt = 0;
        for(int j = 0 ; j < l; j++) {
            if(s[j] == 'o') {
                mask = setBit1(mask, j);
                cnt++;
            } else {
                mask = setBit0(mask, j);
            }
        }
        //cout << cnt << endl;
        cout << cnt - PebbleSolitaire(mask) << endl;
    }
    return 0;
}