Submission #517641

---

Source Code Expand

#include<bits/stdc++.h>
#include<random>
using namespace std;
static const double EPS = 1e-9;
static const int mod = 100000007;
typedef long long ll;

int n;
string s;
deque<char> q;

int dfs(int i){
	if(i==n)return q.size();
	int res = 0xffff,c=s[i];
	if (q.empty()) {
		q.push_back(c);
		res = min(res, dfs(i + 1));
		q.pop_back();
	} else if (q.front() == c) {
		q.pop_front();
		res = min(res, dfs(i + 1));
		q.push_front(c);
	} else if (q.back() == c) {
		q.pop_back();
		res = min(res, dfs(i + 1));
		q.push_back(c);
	} else {
		q.push_back(c);
		res = min(res, dfs(i + 1));
		q.pop_back();
		q.push_front(c);
		res = min(res, dfs(i + 1));
		q.pop_front();
	}
	return res;
}

int main() {
	// freopen ("input.txt", "r", stdin);
	// freopen ("output.txt", "w", stdout);

	cin>>n>>s;
	printf("%d\n", dfs(0));
}

Submission Info

Judge Result