srm625H.cpp

// {{{ $VIMCODER$ <--------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <cmath>
#include <queue>
#include <unordered_map>
#include <numeric>
#include <set>
#include <cstring>
using namespace std;
// }}}

class ConundrumReloaded {
public:
	string anss;
	int n;
	string btoc = "LH";
	int dp[50][2][2];
	int minimumLiars(string answers) {
		anss = answers;
		memset(dp,-1,sizeof dp);
		n = answers.size();
		int res = min(dfs(0,0,0),dfs(0,1,1));
		return res == 100?-1:res;
	}

	int dfs(int pos,bool isLiar,bool fstIsLiar) {
		if(dp[pos][isLiar][fstIsLiar] != -1) return dp[pos][isLiar][fstIsLiar];
		if(pos == n-1) {
			bool last = isLiar ^ fstIsLiar;
			return anss[pos] != btoc[last]?isLiar:100;
		}
		int res = 100;
		if(anss[pos] == 'H') res = min(res,dfs(pos+1,isLiar,fstIsLiar)+isLiar);
		else if(anss[pos] == 'L') res = min(res,dfs(pos+1,!isLiar,fstIsLiar)+isLiar);
		else res = min({res,dfs(pos+1,isLiar,fstIsLiar)+isLiar,dfs(pos+1,!isLiar,fstIsLiar)+isLiar});
		return dp[pos][isLiar][fstIsLiar] = res;
	}
};