SRM #528 Div.1 Medium - SPartition

出典

TopCoder Single Round Match 528 - Div. 1 Medium

概要

{x,o}^*を順序を変えずに抜き出して、残ったのと同じ文字列になる場合の数を求める
今何文字目かと、片方だけ取った文字列でメモ化再帰
二等分してそれぞれ全列挙してくっつけてもいいらしい

ソース

#include <string>
#include <map>
#include <iostream>
using namespace std;

class SPartition {
private:
	string str;
	int n;
	map<pair<string, int>, long long> memo;

public:
	long long getCount(string s) {
		str = s;
		n = s.length();
		
		return solve(0, ""); 
	}

	long long solve(int i, string x) {
		if (x.length() > n - i) {
			return 0;
		}
		if (i == n) {
			return 1;
		}
		
		pair<string,int> key = pair<string,int>(x, i);
		if (memo.count(key)) {
			return memo[key];
		}
		
		long long ret = 0;
		if (x.length() == 0) {
			ret += solve(i+1, string(1, str[i])) * 2;
		}
		else {
			ret += solve(i+1, x + str[i]);
			if (str[i] == x[0]) {
				string nextX = x.substr(1);
				ret += solve(i+1, nextX);
			}
		}
		memo[key] = ret;
//		cout << i << "," << x << ":" << ret << endl;
		return ret;
	}

};